Your email is received on your behalf and stored by your ISP until you retrieve it. Quotas are applied to mailboxes on the ISP's mail servers.
There are two ways that your email program communicates with the ISP mail server - POP3 and IMAP.
Here's a table of the differences between the two, but the principal difference of importance in this situation is how they treat the message storage location.
With POP3, your PC is the primary message store, and messages are downloaded to your PC and simultaneously removed from the Server (unless you explicitly change the setting, and the server supports maintaining a server copy).
With IMAP, the server is the primary message store. In addition to leaving all the messages on the server, you are also given a choice between downloading them and leaving them on the server, or downloading them and removing them from the server.
From what you say it would appear that you have an IMAP client, resulting in the messages being stored on the server, and your quota being exceeded.
How you delete the messages on the server depends on which version of Outlook you are using - Outlook or Outlook Express. You can easily check the Help, and look at the MS website.
You may also be able to access your email account using a browser - webmail, or similar. This might be the simplest way to directly manipulate the mailbox on the server.
SD