We have a similar issue here. A combination of old employees, as well as addresses that were never employees in the first place (either someone filled out a form with a nonsense user at our domain, or some spam just makes it up).
I have turned off the auto-response of delivery failure notification in the Exchange System manager, but tracking our spam collection, I can see that it is still is sending out non-delivery notifications... so I'm at a loss on that one.
I would love the ability for Exchange to say "if there is mail coming in and it isn't to a user that exists on our server, then just drop it at the door and don't do anything at all with it" - but that doesn't seem to be the case on ours, even after I've toyed with the settings.
I even setup an EventSink to drop all mail that comes in to certain users, but even that seems to fail (well, not fail, but it apparently gets triggered too late and the non-delivery messages are already sent out).