I have a user that was accidentally deleted from Exchange/AD a few weeks ago. I recreated her account from scratch instead of restoring it. Some of our users are having problems sending to her now. See the following error message. Knee jerk reaction is users are using cached mode and for whatever reason their GAL isn’t updating, but not sure. I believe it works for me because I've for a manual GAL Update. I did a manual force on another user but the problem persisted. I use Outlook 2010 and they use 2007. Shouldn't make a difference, but it's another variable.
Generating server: CAS Server
IMCEAEX-_O=Mail_OU=EXCHANGE+20ADMINISTRATIVE+20GROUP+20+28FYDIBOHF23SPDLT+29_CN=RECIPIENTS_CN=User@domain.org #550 5.1.1 RESOLVER.ADR.ExRecipNotFound; not found ##