This probably has to do with not having public reverse DNS records set up for the server sending the mail.
Check that you have set up a reverse DNS record for your server, and that the address it reports to send from (after any SNATting, etc) can be resolved and reports the correct domain of the sending server.
Wouldn't it be easier to just forward the ex-employee's mail to the appropriate CURRENT employee that is now responsible for the ex's tasks?
I would think that an autoresponder and a forward is all you need?
UPDATE:
Your hosting company not sending NDR's is actually a "good idea". Basically what they're trying to prevent is "backscatter". More information about backscatter can be found here:
http://en.wikipedia.org/wiki/Backscatter_(e-mail)
The main problem I see with what you're trying to do (ie. set up your own server) is that you might be better served with a simple auto-responder rather than a whole new server just to send out bounces.
Is there a particular reason why you want to "bounce" the message rather than just tell the sender that the employee is no longer with you?
The next problem is a little more difficult... LEGITIMATE email with typos that don't bounce back. No bounce means no error, right? Unfortunately no. But to get around the problem you really want to look at the problem closer.
YOUR SERVER should NOT be bouncing the message back to the sender. The SENDER's server should be the one bouncing.
For example, the sender sends an email to jon@domain.com instead of john@domain.com. His server then connects to your server. Your server should immediately say "We don't have a user by the name of "jon@domain.com" here. The SENDER'S server should handle the bounce.
The only bounces you should really be concerned with are bouncing back to your own users.
Please note that I have over generalized this A LOT so before I get a ton of replies from people picking holes in this please take that into consideration.
More information about bouncing, spam, backscatter, etc. can be found here:
http://en.wikipedia.org/wiki/Bounce_message
Email and spam is a twisted world. There is no 100% solution right now.
I learned about backscatter the hard way when I client of mine's email server ended up on several blacklists. It seems that the server was being used to backscatter spam all over the place and the (misconfigured) email server was sending out thousands of bounces.
The immediate fix (and the only way to get off the cursed lists) was to just drop the emails silently and do NO BOUNCING.
Later on the server was configured to only bounce to local recipients.
For simplicity sake, bouncing emails is basically just a specialized form of autoresponder. In your situation I think you could easily get away with setting up a simple auto-responder for your ex-employees and then forward the email (or not) depending on the content of your auto-response.
I hope this helps.
Best Answer
It looks like the behaviour you describe is default for the SMTP service in IIS and can't be changed:
http://www.microsoft.com/technet/prodtechnol/WindowsServer2003/Library/IIS/6bb0d71f-d3d7-4f59-aa01-4d5c022274a4.mspx?mfr=true