I gave up and decided screw them, I don't need to talk to anyone with an ATT address, and bounce messages from them with an explanation.
- You have to ramp up sending from new IP addresses VERY slowly if you want to avoid getting grey / black listed by Yahoo and AOL, this makes it quite a tedious process
- Make sure you also have rDNS set up, Gmail uses it as an important quality signal
- Accurately handling bounces is a bit of a nightmare because each mail server has a slightly different format and you want to make sure you don't process out-of-office messages
- Bounces and "message delayed" messages can arrive days later
So we ended up switching to mailgun and although they do sometimes give you a bad IP the time saved is worth it, especially their option to have a web hook back to your backend to process the bounces.
Until then, all is fine I agree.