There are two levels of permissions that need to be correct for a user (other than the owner) to access folders in outlook. If you want another user to access the entirety of your Mailbox they have to have Owner permission given to them specificallyin the permissions of the mailbox through the Exchange Administrator. As long as the folder permissions have not been changed in the Mailbox (through Outlook) then this should let them in.
Next (as the orginal owner) you need to check the permissions for each folder in Outlook to make sure that the Default has not been changed from when the folder was created. If the Default user is anything other than None then there will be problems accessing the folder.
One thing to remember about setting permissions on Outlook folders. Setting them on an upper level folder does not migrate to the other folders. Thus if you change the permissions on the Mailbox folder it does not grant access to any of the sub-folders (like Inbox). Any 'Owner' of the exchange mailbox should be able to access all Outlook folders.
As for the log entries you see on the server. These are normal entries that Exchange makes whenever another user account opens a mailbox that has not been 'directly associated' to the user account. (this is not the same as granting permission)
Your message here indicates that you need to look more closely at the individual folder permissions.
Hope this helps...