Yes, before I brought this question to Slashdot, I did my homework first. I've scoured logs, check RBLs, used wireshark, etc. It's definitely not a misconfiguration on my end or an issue with complaints resulting from spam. The traffic coming from my server is so ridiculously small, that I was shocked to begin getting messages like these from those email providers.
The only conclusion that I can draw is that these major providers all use the same dynamic, or what they interpret as dynamic anyhow, IP lists and block based on them. I can understand that... the part that I have an issue with is that I have no recourse to have my IP reevaluated.