First off what sort of e-mail account are you using with it, POP or IMAP?

If it's a POP account then it's likely that you have your normal (PC) mail software set to "leave mail on server".

If it's IMAP then you are probably making messages for deletion but not purging them.