Updated!
I'm starting to feel comfortable with this app now... http://www.iphone.r4m0n.net/?p=11

And I think the Mail.app stores the read mails locally, just not sure for how long...

If you could get it to delete using the same stuff you have already used that would be awesome. I'd love to help out (however I don't have much coding experience at all and I would be lost).

You mean deleting all mail in a mailbox? I guess it would be quite easy to delete locally, but to delete from the POP/IMAP server would be a very different matter... Which one do you mean?

I see what you're saying. Deleting locally would be great even. So the emails don't show up at all.