Hoople - 5:40 am on Apr 12, 2013 (gmt 0)
A little more detail might be helpful like:
is your server a shared hosting y/n
DNS passes online health checks that test email portions?
Is the IP address on ANY blacklists? see mxtoolbox to check
Is the email server in an IP block marked as 'portable'? (for end user devices)