I haven't cared much until now. I've been using Spambayes and it's been wonderful now that it's sufficiently trained and all. But recently I've been having another problem.

Recently I started getting emails from AOL saying that I had returned or undeliverable mail. I look inside these messages and find that some asshole has been spamming using fake addresses from my domain name. Well, this was irritating, but I still wasn't angry because at least AOL was kind enough to group a massive amount of these instances into a single email. Some days I'll get 2 or 3 of these things, some days none.

But just now I tried sending a legit email to someone on AOL, and my entire domain is blocked!

What do I do about this? Is there anything I can do? Is there something really simple that I'm not seeing?

I think AOL has switched (or is switching) to a DNS challenge for accepting mail. There are three competing proposals for this, and I don't remember which one they chose. Google is your friend.

Whichever they're using, it may just mean that you need to add some special records to your domain info, so that they can verify incoming mail claiming to be from your domain, is in fact, from your domain.

Cheers

Are you trying to send email from a dialup or DSL/cable account directly without using the ISPs mail server? If so then AOL will refuse to accept email from you. In theory you can tell your ISP who will then pass the message onto AOL to whitelist your IP address as a valid mail server.

There is a spammer who picks random domains and then adds random usernames to the start. The domain belonging to a friend was picked a few months back - it was set to catch-all and got a few thousand bounces before I turned off catch-all, and then it was still rejecting thousands a day when I checked weeks later. The bounces were coming from hijacked/comprimsed machines which had been blocked by AOL - they weren't coming directly from them.

The addresses were like:
julias_caesar@ friendshijackeddomain
hugh_g_rection@ friendshijackeddomain

Gareth

This is mail being sent through my webmail, which I use quite often when I'm at work or out of town. I had someone contact me from an AOL address, but I can't respond to them now.

One of the links in the error message took me to a page on AOL that said something about a mail loop. Should I set that up with them?

I get this too on my demon account. It's really beginning to piss me off.

Do you run your own SMTP server on your DSL/cable line though?

I look inside these messages and find that some [censored] has been spamming using fake addresses from my domain name.

Are you sure it's spam? Most new viruses will randomize both the "to" and the "from" address in their payload emails, and they get their list by scanning the hard disk for emails. Perhaps someone who's got your email address on their hard disk is infected with a virus? Of course, there's no way to determine who.

On a somewhat related note, some kind individual spoofed a range of addresses my work uses (203.185.x.x) and sent out a mass of spam. Subsequently, this range was put on the SPEWS list.
Now we have clients ringing up saying that their legitimate email is being blocked by recipients on this system.

Blacklisting a domain based on From: or Reply-To: fields in spam messages (or even HELLO response string - IP is probably OK, but that's just the last hop) is utterly moronic. Everybody's grandmother can spoof those.

I am afraid we will have to switch to some kind of authentication rather soon, with all unwanted consequences for privacy; otherwise, e-mail will become useless... One good idea I saw a few months ago is to only have originating SMTP server authenticate itself (its domain--sign it together with timestamp and message ID and hash or something like that); user could still be anonymous (for the rest of the world, anyway). It would then be the originating server's responsibility not to send spam.