1.) After deleting an e-mail close Windows Mail and log into the e-mail account through the web interface, or another client if it is not available through a web interface. See if the e-mail is still there or if the copy is simply residing on your hard drive and not on the server.

2.) Go Tools->Accounts, select the account, click Properties, and choose the Advanced tab. At the bottom there is an option to delete the e-mail from the server when deleted from the client...enable it or disable the leaving of a copy on the server entirely.

Hope this helps,
John