Hi RT,
Sounds like a really odd problem.
So, if I understand it correctly, User A has a mailbox that they wish to allow User B to open and use.
The first thing I would try is have User A take away rights for User B and then grant them again. This should verify the permissions are granted and everything gets reset.
How did you grant permissions? Did User A Grant the rights from the mailbox or did you do it from the Exchange Server?
Best method is Right Click on the Mailbox in Outlook, Properties, Permissions, Add. From there select the user and then the rights.
Here is another idea from the server side. (might) apply.....
http://support.microsoft.com/kb/839531