Is it not acceptable to just remove the user from Exchange and add the termed users SMTP address as an SMTP proxy? That would hanlde all external mail
If internal mail is a problem then all you need can take the legacyExchangeDN of the termed user and add it as an X500 proxy address. If you don't know how to created an X500 address just chose a custom address and where it says "type" input X500 in that field.