You are correct that deleted mail is stored in a local folder. In order to delete the deleted mail you will need to compact Outlook Express. I realize you did not mention being asked to compact OE but the info below is valid.
This article Why You Should Let Outlook Express Compact Messages When It Asks You
explains explain exactly what compacting messages is, and why you may be seeing that message. It's possible that you don't have a lot of kept mail; however, OE stores messages within a database, which tends to grow in size and degrade the perfomance of OE. Even previously deleted messages that are removed from OE take up space in that database. Compacting your folders will REMOVE all the records that you have deleted. It may simply be a case of to many so called deleted messages are sitting somewhere on your computer, taking up drive space. This is explained in more detail in the section "What Does Compacting Messages Mean, and What Happens
To manually compact OE:
Open Outlook Express.
Click on the "File" menu in the Outlook Express window and then click on "Folder."
Click on the "Compact All Folders" option. The compacting process will start.
Edited by Queen-Evie, 19 February 2012 - 08:59 AM.