do you have reverselookups on your external IP's? In the primary DNS for the domain, make sure there is a Pointer (PTR) record for each external IP address. (These records are also known as in-addr.arpa entries.)
Problem can be Ident aswell. Or no reverselookups on your official IP's.
