Email won't stay deleted I mostly use my computer for email, but obviously when I'm on the go it's good to have my email accessible at all times. That's what the email app is for, right?

So I have it set up to download emails, but to never delete them from the server. Essentially this is the same as I have on my laptop. Only my main computer is set to delete emails from the server when I delete them from my inbox.

The point is, while this works fine on my laptop, my phone will keep downloading the same emails, even when I hit the "Delete" button to remove them from my phone's inbox. Strangely, though, it will only do this a few hours after they were deleted (the mailbox is set to update every 15 minutes), and usually only when I receive a new email or two.

In other words, when I get a new email, the phone will start downloading some old emails seemingly at random.

What gives, and how do I fix it?
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).