Yesterday I removed a user from our BES since he was having issues getting his contacts to sync and last night all of his contacts in Outlook are now gone. I've checked his PST file and found nothing. I'm working with him now to see if there's anything in Outlook under Recover Deleted Items (which I'm doubtful). He has a desktop in LA that I'm going to check, but besides restoring from a backup of Exchange, is there any other options?

Most important question is how is this even possible? I've done this exact same thing hundreds of times with no problems at all.

Help is greatly appreciated...

PST Files and Exchange? Something doesn't compute.

It's not possible.
There's no way that removing a BES account deleted the user's address book.
Something else happened, and it wasn't BES related.

Since his contacts wouldn't sync prior to removing him from our BES, would having Outlook in cache mode possibly make a difference?

nope, cached mode shouldn't make any difference. we run users in both modes. my guess is that outlook had no contacts when you thought it wasn't synching them. When was the last time you know there were contacts? i'd look for the backup tape from that date, restore the mailbox, confirm the contacts exist, then try to activate again.

I have never seen BES remove contacts cached or not.

User did something and not telling you everything.