You need to set the deleted items retention (it's on the properties of each store).
Items won't be deleted until the items have been removed from the dumpster which happens after the period specified.
If you want to create white space quickly set the deleted items retention to 0 and then set the maintenance schedule to run every 15 minutes.
Restart the Microsoft Exchange System Attendent service and then give it 30 minutes or so.
Look in the event log for event 1221, there may be 2 one for the public and one for the private store, this will tell you how much free space there is.