The gibberish name ones may be targeting backscatter. They might have a reply-to with the address they're really targeting.

And that may have dropped off because there was a concerted effort to make it harder to do that around then. In particular, that's kind of what killed qmail as an in-vogue MTA, because it wasn't being updated and you had to use awkward patches to stop backscatter.