It sounds like you are set up with P.O.P. e-mail, which allows you to delete your e-mails from your phone, but will not delete them from your e-mail server. When your e-mail syncs, what ever is sitting on your server will be pulled back to your phone. If you set up your e-mail using IMAP, when you delete an e-mail from your phone, it will also delete it from your e-mail server.
I think that's right (might be backwards). If not, someone will correct me shortly.