Have either of you tried to login as BESAdmin on your server and use the "Edit MAPI Profile" icon in the Blackberry program group?

Just curious because it sounds like the problem.

[edit]
Sounds like you probably did this already.
[/edit]