You set both at 0 (zero) for both keep deleted items for days and mailboxes for days. Also make sure you didn't have Do not permanently delete boxes checked.
Then apply then expand the Mailbox database then right click on Mailboxes then select Run Clean up Agent
This has worked in the few instances in the past I have run into this issue.
http://support.microsoft.com/kb/930363