I will update this page with results of suggestions and tests done.
I posted this on Slashdot to solicit help:
What if this happened to you? Mysteriously and suddenly, three weeks ago (Mar 26) my mailq filled up with "Connection timed out" messages. I am running up-to-date gentoo on an intel box. About 10% of my outbound messages were just pooling up. Suspicious, but thinking maybe the receivers were broken, I waited a few days. Nothing improved. traceroute 25 got through. telnet 25 timed out. Then I discovered that using a different IP address in the same /24 I could get through. Suddenly it started to feel like my IP address had been blacklisted, and I was being filtered at the receiver firewall. Here I sit three weeks later, using the % address hack and a relay machine to email 10% of my world. So, dear /. friends, what could be the cause? I am officially clueless. Have I been blacklisted? How can I check? If not blacklisted, what else could account for this set of facts? It's driving me nuts.
Note that the filtering all started at the same moment, so far as I can tell. The same moment, and at strangely different locations. What is the common factor?
Which IP addresses get through successfully? 188.8.131.52.
What destinations are letting email from .10 time out, but not yet checked for mail from .11? cwconnect.cingular.com
What destinations are getting email from .10 okay? aol.com appstate.edu byu.net byui.edu comcast.net cox.net earthlink.net gmail.com hotmail.com icsun.ithaca.edu juno.com mail.nwmissouri.edu merrimack.edu msn.com quinnipiac.edu ryerson.ca satx.rr.com sbcglobal.net txstate.edu uncw.edu usouthal.edu verizon.net yahoo.com
I suspect some minor spam blacklisting service has added me to its black list. I suspect the sites that are filtering my email are using the blacklisting service to make a firewall for port 25 traffic from blacklisted IP addresses.
I further suspect that the sysadmins at these blocking sites may not even know it is happening because it could be part of a spam blocking package someone purchased.
Anyway, that's my best theory at this point. I have nothing to actually confirm or deny it. And I have no other theories that fit the facts.