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)?