YES means compress, not eliminate. It just uses a software routine to eliminate extra spaces and use special codes for repeating characters so the messages use less storage. Those emails should still all be available. They simply reverse through the same algorithm to decompress.
In Outlook Express, click on the 'tools' tab. Choose 'options'. Click on the 'maintenance' tab and see what your settings are. The only thing checked on mine is to Delete News Messages 5 days after download. If the first box, 'Empty deleted items on exit' is checked, that might explain why your deleted messages are not in the 'deleted' folder. Again, they will NOT be in your Windows Recycle Bin.
Hopefully some helpful information??
Edit to add: The only way I know to see how much storage I'm using for my mail is to go to Hotmail. There it tells me very clearly. I tend to start cleaning things out if I'm even approaching 50% -- that way I always have room for emails with large picture (grandchildren!)files, etc.
Betty