you difinately need to upgrade SP, there are lots of issue to resolve this issue.
however form what you are saying it seems this works on one device therefore this maybe an issue with permissions.
didn;t catch your exchange version.
make sure its not a member of any groups within AD as it probabily has an explicit deny from group membership.
can you provide the following
exchange version and SP
group membership of the BESadmin account
MAPI and CDO version
how many exchange servers and whether the effected user is on a different exchange server from the person that works
from this, would have a good idea where the problem lies
