Email won't stay deleted
There are multiple approaches to this problem. The first an most effective is to switch from POP3 (which I assume from your question you are using) to IMAP, where mail is handled on the server instead of client-side -- so you can delete a message when you decide to delete it (and not when client X is retrieving it, as handled by POP3).

Second might be trying a different mail client (again, I do not know what you are currently using). For Android, I'd recommend K-9 Mail -- which is capable of handling POP3 as well as IMAP, and even Exchange (the latter via WebDAV).