Ok folks I need to rehash this question again. I had the users cleanup their emails and the mailboxes have shrank significantly but I'm still getting this message.:
Exchange store 'First Storage Group\Mailbox Store (MYMAIL)': The logical size of this database (the logical size equals the physical size of the .edb file and the .stm file minus the logical free space in each) is 72 GB. This database size is approaching the size limit of 75 GB.
If the logical database size exceeds the maximum size limit, it will be dismounted on a regular basis.
Why has the size not shrunk? Is there a step I'm missing here? Need help..