Exchange uses single instance storage in the database. Deleting mailboxes won't make any difference to the amount of mail stored in the db unless the mailboxes you delete are the only mailboxes that are storing those messages. Example: user 1 sends a message to user 2 and 3. User 1 has a pojnter to the message in his send items, and users 2 and 3 each have a pointer to the message in their inboxes. The server stores 1 copy of the message in the db. What happens when you delete mailbox 1? Nothing - the message is still stored on the server, because users 2 and 3 still have pointers to it. In this example you would have to delete all three mailboxes before Exchange would remove the message from the db. (Or have all 3 users 'delete' the message from their mailboxes, and then the message will eventually be deleted.)
Even if you have some messsages in your db that are ready for deletion, the deleted item retention period (if you have it set) will stop them being deleted immediately.
You can check how much 'white space' (empty space that can store new messages) in your db by checking the application event log for 1221 events - one each for the priv and the pub, written by the overnight maintenance. The edb file will only be extended when the white space is all used up, otherwise new mail just goes into the white space and the file doesn't get any bigger.