How do I remove the deny for the administrator to have full access to a users mailbox?

Use ADSI edit (from support tools) to remove it from the storage group or administrative group. The mailbox gets the deny from the DB, which gets it from the SG, which gets it from the administrative group. Make sure you've got a good sysstate backup of your gc/dc before messing around in adsiedit

You may want to take a peek at this article. http://www.petri.co.il/grant_full_mailbox_rights_on_exchange_2000_2003.htm