Does anybody have any insight into " at least as difficult if not more difficult than writing a database engine"? It would seem to me that a mail server would be much easier than a database engine.
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.