Your intentions are honorable. That said, I would NEVER EVER EVER do that. The reason is that you will end up putting yourself on spam blacklists and unable to send mail, since you'll be rejected due to your presence on these blacklists.
For example, lets say I am a spammer. I try to send a bogus message thru your server, send 'helo bla', and give you a sender address of "firstname.lastname@example.org". You reject my message because of a non-fqdn hostname. But, you also send "email@example.com" and poor old "firstname.lastname@example.org" a notification. To them you appear to be spamming, since they never ever sent you an email to begin with.
This will end up happing hundreds of times a day, with you sending out hundreds of notifications to innocent users. Sure a couple of them are misconfigured exchange server, but the rest are not.
My advise is to leave it as is. When a legitimate user tries sending an email that gets rejected, you'll hear about it from your user(s) - believe me. Then you can school the MS Exchange admin on how to properly setup his exchange server. Chances are he's being rejected by other SMTP servers, and you're doing him a favor by enlightening him.
Last edited by WindowBreaker; 10-13-2006 at 10:27 PM.