Quick rundown: we recently migrated exchange and DNS servers, I don't think this has much to do with the problem. Our domain's MX records point to a 3rd parties IP that filters spam for us then forwards cleared messages to one of our public IPs. Our outbound SMTP traffic goes out of the same public IP the 3rd party forwards to, but there is obviously no MX record.
Now we are starting to get blacklist/HELO bounce back errors from a few domains. This has everything to do with our outbound SMTP and MX records being different, no? Do we pretty much have to unify the IPs or is there some work-around?