If I may throw myself into the fray, I'll tell you what I've found this to be 90% of the time (and Dyadmin, you're pretty close...)and it's not open relay:
1) Spammer finds out about your domain, let's COMPANY.COM (this isn't hard to do as domain names are public knowledge)
2) Spammer sends mail(s) to some arbitrary name at COMPANY.COM that winds up being invalid. Of course, the Spammer sends this email using a bogus return address.
3) Exchange accepts the mail, since it's sent to the proper domain name, then discovers that the actual user part is not valid.
4) Exchange uses the bogus return address to try and send an NDR. At the same time, Exchange strips away the sender address, leaving it as <>. This is done to prevent Exchange from going into an endless loop, as it would be constantly reporting back to itself that it's own NDR was undeliverable.
5) Eventually, these messages time out in the queue and should be deleted.