D'oh! I knew this, but it's been so long.
They are indeed blocking port 25. A simple telnet to 1025 indicates so. I thought it seemed awfully firewally.
I think I remember dealing with this a while ago, now that you mentioned that. For what it's worth (really for the sake of forum searches), the ISP is Earthlink.
Ah, spammers touch us in so many ways. I wish I just return the favor to them, (with an iron pipe).