How to add an alias for a mailbox that was just purged from Exchange 2003

We are running Exchange 2003 Standard in-house. The Director of Operations has just let two staff members go, and would like e-mail sent to their addresses sent to him. Here is what I have done so far:

The two staff member's Active Directory accounts have been disabled.

Their mailboxes have been deleted and purged from Exchange.

I've added their e-mail addresses as SMTP aliases to the Director's Active Directory account.

However, when trying to e-mail these addresses, I get a local "NDR" telling me that the mail account doesn't exist. I've used aliasing extensively (just never for this reason) to provide additional e-mail addresses for employees (such as when they get married and change names, or need temporary mail addresses, etc.), so this is not new to me. However, I don't understand why this isn't working.

Is it because these addresses used to be associated with an Active Directory account and Exchange has yet to purge them from the GAL? The old accounts are still showing in the current GAL, but if I look in System Manager > Recipients > All Global Address Lists > Default Global Address List > Properties > Preview, the two accounts in question do not show up.

Do I just have to wait until the next update interval? Is there a way to force this update to happen?

Update:

Upon further research, I'm able to send these e-mails while using a client that isn't running in cached mode, and they end up being sent to the primary address for the account they are assigned to. Trying to send to these former addresses while using cached mode results in the message being rejected. Pretty positive this has something to do with the GAL on these cached mode clients. The clients we are using are Outlook 2003, 2007 and 2010 and it is policy to use cached mode on all Outlook clients.