I have an issue with a client NOT receiving RANDOM undeliverable emails. They are using SBS 2003 (Exchange 2003).
On rare occasions, after a reboot, users will receive OLD undeliverable emails that were originally days/weeks/months previously.
I can't reproduce the problem - ie. I send an email to a known bad address and it comes back immediately.