It is important that all IP addresses in your network (particularly mail servers) have valid and correct forward and reverse DNS which agrees (paranoid reverse DNS). Many sites will bounce mail based solely on lacking DNS information.
Abuse.net maintains a database of contact addresses at various Internet Service Provider, which should be used when reporting spam or abuse issues on their network. Your primary domain name(s) should be registered with Abuse.net.
[Append to This Answer]