@Omondi, IMO the main core problem of most mail server setups is REVERSE DNS. If this is not done correctly, you will always get problems. Rule of thumb is this : If your Reverse DNS is an Ip address, mambo mbaya! Pls check this first, use something like  Mxtool. Have you done this check and is reverse dns a domain/machine name? HTHs.