first the auths cache clearing is almost ever used… just there for when something weird/unique happens… and works in some testing I did this morning… at least on my test sites 
bigger question would be why are they 0 anyways… there is no real facility within SP for setting them zero for admins… that is the confusing part and this is first such report…
so for this user, can you also look in the sfmembers table and see what they have in the memberships column?
also, can you try uninstalling the private messaging plugin and then reactivating it? see if we can coax it into updating those permissions..
