Or, in your account-settings, do you have the option for "remove (emails) from server when removed from Deleted Items" not ticked?

Tools -> Accounts -> Properties (for your mail-account, click on it to highlight) -> Advanced

Either make sure "Leave a copy of messages on server" is NOT ticked, or if you'd prefer to leave them there in case you need a format/etc, then make sure either of the "remove" options below are ticked aswell...