Thanks a lot for the quick response. You've provided lots of good information and hope. I'm sort of middleman for the Exchange Admin that got saddled with this problem. He asked me to check out the Blackberry angle, so I don't yet have the answers to all of your questions, but have passed your guidance on.
I've already have just received a response that this has already fixed up one problem user, so again thanks!
Unfortunately, the execs involved haven't been real thrilled about having their BES accounts removed/recreated, but the brighter side is that your Exchange info, (which I'm not strong on) is helping a bunch.
If you're ever in NC, the beer will flow like wine (or some better metaphor : )