No, that's not the way it works.

iPhone and Android mail apps can use either POP or IMAP mail protocols.

With POP, the phone downloads emails to the device when you check mail. You have the option to have emails deleted from the server upon download, or left on. Most POP users leave them on the server as a backup, so they can be downloaded to a computer later. When you delete the copy of the email that's on the device, the server is not altered. When you check again later, the phone knows which emails you have already downloaded, even if it's already deleted from the phone, and does not re-download them.

With IMAP, an email only downloads to the device when you open it - it stays on the server till then. And it only downloads in the same way that a web page downloads when you're viewing it in a browser - a temp copy on the device which is non-persistent. With the IMAP setup, what you're really doing is remotely viewing and manipulating your mailbox on the server; delete an email from your phone, and it's deleted from the server. I don't think the phone retains any 'trash' copy, though I believe that the server has a trash folder for recovering deleted mails.

But the iPhone mail app does glitch once in a while. I used the POP setup on mine, and had it re-re-re-try to download my emails a few times, giving me 2 or 3 copies of the same headers with no emails behind them, and it wouldn't delete the headers. Fortunately, the problem was corrected within a few hours, and I had an unlimited data plan with AT&T anyway, so it didn't do anything more than inconvenience me. This problem happened to me about 3 times over the 26 months that I used my iPhone 3GS.

For personal mail, I still use the POP setup on my Android. My mail is downloaded to my computer when I get home, so I really only use the phone as a temporary cache to view my mail on the go; all true email interaction is done at home on my PC.