Dr.Hipp mentioned GMail bouncing email sent to him - but hosting email yourself, will just move you to a different side of the bounce - now GMail will be bouncing emails sent by you! See, for example, first comments on the recent HN thread here: https://news.ycombinator.com/item?id=27707857 (ctrl+f for "pain in the" if it's not the first one).
So it looks like convincing GMail to respect your small server is a non-technical problem, which might be an issue for a person with "only engineering" mindset. On the other side, Dr.Hipp looks like a right person to try to convince GMail to respect smaller mailservers!
On the other hand, AT&T is most definitely a problem. They run their own internal RBL, and the best I can guess is that they're blocking Linode. Any mail I send to an AT&T customer gets bounced, and forwarding that bounce to the address they indicate it should be sent to to get delisted accomplishes nothing.
This is also a good reason to keep a VPS even if you aren't using it at the moment: it keeps the IP "clean" so that when you put it back into use, it is useful, as opposed to (possibly) some random IP that up until a month ago was spammer central.
That won't protect you from the block getting on a blacklist though.
Emphasis here?
Counter-argument moving vms to different providers, ips etc is a lot more straightforward so maybe they don't "control" your mail..?"
And a third way of looking at is every mail has two endpoints. You don't control the server of who sent it to you or who you send it to. Google does. So they still control your mail..?