Read up on "backscatter spam".
This is a deliberate attack on your domain.
How it works:
A spammer uses infected home user boxes to send random mail to various
domains, with fake random addresses in your domain as the from or
reply-to address.
When the target domain of the initial domain does not do recipient
validation at the smtp connection stage (as it should do), but spools
and then rejects the mail - to you, hence you are the real target.
Greylisting is of no use whatsoever because the servers sending the
bounces to you are actual smtp boxes (sendmail, extrange, ....), not
malware, so they will quickly bypass spamd. Spamd greytraps will help a
great deal, but you say that the addresses are random.
How to cope with it:
All you can do is make sure that you reject mail for unknown users at
the smtp connection stage. You can rate limit most mail daemons so they
don't overwhelm your box. Don't worry about it, I sometimes have up to
1300 messages a minute hitting my PII 350 box on a 500M ADSL and can not
tell the difference when surfing about.
How to run a mailserver:
Reject mail for unknown users at the initial smtp connection stage.
For valid users; either reject spam at the smtp connection stage, or
spool it, process it later, tag it as spam and deliver it to the user's
spam box - do not bounce it later as you will then be generating
backscatter for some other poor soul.
Note: some versions of exchange can not do recipient validation at the
smtp connection stage, so this will always be a problem, and is yet
another reason never to have exchange as an internet facing mail server.
