The problem might be resolved by cleaning up the junk or deleted email (btw: Outlook Express folders are limited to 4096MB in size and the .dbx to 2048MB). If you look in the folder where the dbx files are stored you should find the problem (empty folders in Outlook but there's a mismatch in dbx file size etc).
The path of the Outlook Express folder is C:\Documents and Settings\<User>\Local Settings\Application Data\Identities\{GUID}\Microsoft\Outlook Express