Basically, when we installed Exchange 2010 alongside our Exchange 2003 server (we assume), this is what caused our problem. The Exchange 2010 server is not active, just running on the domain.
What's actually going on is that user groups like Enterprise Admins are getting a single deny flag on Full Control over mailboxes currently residing on the Exchange 2003 server which is preventing any of us from making changes.
It says these permissions are inherited from the Parent Object, but we have no idea which one that is.
Any idea on how to go about fixing this?
This should actually be the default for Exchange 2003. By design, you don't necessarily want your admins being able to read everyone else's email.
The "best practice" if you need the access is to assign a different account (who is not an Enterprise or Domain Admin) with full control permissions if you need them (see this petri.co.il link).