You need to realize that this has nothing to do with your own computer, or how many mails you have stored there. If genuine, this has to do with your mailbox at your provider.
What I'd do is find out if your provider has a browser portal to your mailbox. If so, go there and see how many mails are stored there.
You see, Outlook Express running on your computer is only a user interface into your mailbox at the provider. If you say delete a mail, Outlook Express should tell the mailbox at your provider to delete it. If this doesn't work, mails will accumulate at your provider, rendering your mailbox full. Also, there should be a setting in Outlook Express whether to keep or delete mails at your provider, once Outlook Express has fetched the mail. If not turned on, all mails you've ever received will accumulate in your mailbox at your provider. You might look into how "POP3" works, which is the technology often used for such, it's a protocol by which clients like Outlook Express talk to your mailbox at your provider.
<edit: looks like some of what I'm saying covered by earlier reply ... still keeping in case helpful>