I may be missing the boat here, but if you want a specific message to go back stating that a user is no longer with the company, you could try creating an e-mail user "Old Employees" and aliasing it with the old employees e-mails. Go into an outlook client and attach to this user. Create a rule that states all messages coming into this account, reply with a specified e-mail then delete. Have the e-mail state that the employee they were trying to contact is no longer with the company, if they need assistance, please contact "info@yourcompany.com" or some other general address. After you have done this, hide this user from the address book. (User properties, advanced tab) and let them sit.
I would check with your HR department on proper wording and exactly how they want this handled. You could go back and periodically clean out the alias list with addresses over x months.
Hope this helps.
Tom Backus
Network Administrator
Hitchcock Industries
Bloomington, Minnesota.
backust@hitchcockusa.com