An issue I recently encountered with some mail servers was poor MTA reputation. Even though the servers were only used for corporate email, somehow their MTA is poor at senderbase, even though none of the IP’s are on a single RBL/SBL. This is partly due to Slicehost having bad IP blocks and the method they use for assigning IP’s to new slices. But I believe the issue can be resolved with good history.
Read more