Mailbox Manager Issue with Exchange 2003 - Recipient Policy not deleting ALL messages older than 90 days as we set it

I recently setup a recipient policy for Mailbox Management on our Exchange 2003 SP2 Server.

In Recipients > Recipient Policies we had serveral listed.
 - Policy 1 - Policy that was setup when our email server was setup
 - Default - The default policy
 - New 90 Day Email Policy - This is the one I created last week.
I set the new "90 Day Email Policy" to only be a Mailbox Management Policy that will Delete Items Immediately that are older than 90 days and ANY size.

I left the default for the filter when I clicked which items or mailboxes to filter. This is the LDAP query or filter that I am using...

(&(&(& (mailnickname=*) (| (&(objectCategory=person)(objectClass=user)(!(homeMDB=*))(!(msExchHomeServerName=*)))(&(objectCategory=person)(objectClass=user)(|(homeMDB=*)(msExchHomeServerName=*)))(&(objectCategory=person)(objectClass=contact))(objectCategory=group)(objectCategory=publicFolder)(objectCategory=msExchDynamicDistributionList) ))))

I ran the policy on the server manually and there are still users on the server who have messages older than 90 days in their inboxes. I made sure I selected every single check box from Inbox, Subfolders Deleted Items, Sent Items, etc and told it to only keep messages newer than 90 days.

What would cause the server to keep some messages older than 90 days but delete other messages. When the policy ran it did delete almost 1 GB of old email from a handful of mailboxes but left some messages untouched.