Are you compacting correctly?
http://www.insideoe.com/files/maintain.htm#compact
If still no joy, close OE. Find and delete Deleted Items.dbx in your
identity's store (http://www.insideoe.com/files/store.htm#storemain).
General OE Caveats:
- Don't use Inbox or Sent Items to archive messages. Move them to local
folders created for this purpose.
- Empty Deleted Items folder daily.
- Disable Background Compacting [N/A in SP2] and frequently perform a manual
compact of all OE folders while "working offline". More at
http://www.insideoe.com/files/maintain.htm.
- Your anti-virus application's email scanning feature can also cause
corruption. Disable it. It provides no additional protection.

Signature
~Robear Dyer (PA Bear)
MS MVP-Windows (Shell, IE/OE) & Security
> I've purged my delete folder from OE, yet
> Checking the "deleted items.dbx" file in Ap\ID\#\MS\OE, the folder is
[quoted text clipped - 6 lines]
> Is my OE not working right?
> How do I bring down the size of the .dbx folder?