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