I use a gmail account with Microsoft Outlook 2003. When I delete messages from my Inbox, a line is drawn through the message, but I can't seem to make it go away, so my inbox has thousands of messages.
When you connect to gmail, you're using the IMAP mail protocol. IMAP stores the mail on the server and your mail client (Outlook) downloads all of the necessary information you need (headers, body, attachments) and then disconnects from the server. Typically when you want to delete mail you need to connect to the server and tell it which messages to delete. This differs from the other common mail protocol POP3 where you download the messages from the server and they are (normally) automatically removed at the same time.
Outlook handles the deletion of mail in an IMAP server as a two step process: First, when you delete mail in Outlook it will mark the message as to be deleted by crossing a line through it. Second, once you have selected all of the mail for deletion, you can tell Outlook to then connect to the server (gmail) to delete all of the messages you have marked as deleted. Contrast this to POP3 where you have already downloaded the message from the server. It no longer exists on the server so when you delete it from Outlook there is no follow-up needed.
To handle the second step, do this: On the menu bar, select Edit -> Purge Deleted Messages
I had the same problem a while ago. Here's the answer:
You will have to delete your email then purge them since it's over iMAP.