So I created a new user, put in the normal details, said yes to create mailbox, then tried to share with someone. After an hour of battling cached mode etc etc, I thought to check the permissions of someone else.
Normally under exchange advanced, mailbox rights, you would have a bunch of items: administrator anon logon domain admins everyone mail ops SELF etc
But this one only had SELF!
So my question is, why did it fail to add these permissions (I eventually fixed the problem by adding them in myself)?
The mailbox has not actually been created yet, so inherited security privileges that apply to the mailbox don't show up.
To nudge this process along, get the user to log in to the mailbox or send an email message to it. The permissions will quickly fall into line with what you expect.
The Exchange server only syncs with AD every few hours. The delay is tuneable. It might just be that it hadn't synced with AD yet, so the full permissions weren't there. You can bounce the server to force a sync, but that's a bit drastic.
I had to set the sync interval down to about 2 hours on the server that I looked after, to get around similar problems.
You (or the user) need to log in once to the mailbox for the permissions to be created. I am not sure if the OWA login works this way (never tried it), so maybe try via Outlook.