Yes, obviously I have an FQDN. And yes, I have SPF set up - that was mentioned in my original question up top. No, I do not have DKIM or DMARC set up, but based on a lot of feedback today, I most certainly will by tomorrow morning. Thank you for your input.

This has been done for the past 2 years, so I'm good there.

DMARC is definitely at the top of my list to make sure I have set up after reading about it today. Thank you for the input.

What?? That link you posted references users who are sending email AS yahoo email users, via a server that is not Yahoo. That is not all what my question was about. What your link does show is that those major providers all use DMARC, so that's an interesting item that ties all those providers together.

You forgo the last part of that I assume, the 7.

Yes, I have 5 IPs. It's a pain, but yes, I can try one of the others. In regards to the cable modem - it's set up in a manner that the single outgoing IP for my mail server is directly linked to it. So, when I say I ran wireshark on the traffic, I did so for that IP. It is the only machine on the network that uses that IP. The results were well within what I expected for email traffic. Most of the traffic is incoming spam, and the only outgoing messages are being sent by valid users - and not many of them at that.

I've run SPF for years now, and I pass all the associated tests there. I have a valid PTR record that matches my domain. I do not currently use DKIM, but I guess that's my next attempt at fixing this. DMARC also sounds interesting, I have never heard of that before. I will gladly configure DKIM here and then look into DMARC. Thanks for the information.

I'm the guy who asked the question, and spammer I am not. I hate spam more than most people since I run my own mail server, and have for years. Back before spamassassin, my email server was basically unusable, thanks to the fact my personal email address was associated with my whois record. I'm just a poor asshole who signed a 3 year contract with comcast, and 2 years in, my connection became unusable for relaying email.

Yes, I have proper reverse DNS and SPF records. So, I'm good to go there.

Bummer. I was hoping that earlier post about using Comcast as my relay would solve it.

Exactly. I would love to know what centralized IP blacklist that those 3 providers use.

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.

I have verified. I am not on any RBLs as I mentioned in my original question. As for whether or not my IP range is residential, I was told when I signed up that it was not. However, I have no way that I know of to verify that.

Yep, I've used that site and checked it against that list. 0 results found on the blacklist check.

Wow, I did not know this. This could solve all my issues. Thanks for the information, I'll look this up right away.