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?