On Sep 18, 2013, at 9:07 AM, NANOG <NANOG@abcsupply.com> wrote:
We recently purchased new IP addresses from ARIN
No, actually, you didn't. You were assigned the use of the addresses, based on need. Just as a radio station does not "purchase" spectrum. https://www.arin.net/policy/nrpm.html#four3
Our mail server IP address is 74.112.99.25. Is it possible they are blocking us based on old information from the previous IP address block owner?
Quite likely, yes. John LeCoque's suggestions seemed quite sound:
I would say the first step is to find an immediate workaround for your end users - maybe bring up a VM on AWS or some other cloud provider to use as an SMTP relay while you work out the blacklist issue. If you run into blacklist issues after that, you may want to take a very close look at your outbound mailflow to make sure your organization isn't sending out messages that could be categorized as spam.
-Bill