That's not entirely correct in terms of how IMAP works.
OK - POP3 works by accessing your server, checking for any emails that device hasn't seen before (by comparing it to what it has already downloaded), and downloads any new emails. If you delete an email on one device it does not delete it on any others. Sometimes emails are automatically deleted when they're downloaded, which can cause problems if another device checks for new emails as the new email will have already been deleted.
IMAP works by making the list of emails on the device an exact copy of the emails on the server. This means that if you delete an email on one device, it will be delete on other devices too. If you mark an email as read/unread on one, it will be marked as read/unread on the others, etc.
IMAP and POP3 do not support stuff like syncing of contacts, calendar, etc. These are both email protocols. If you want this kind of stuff you have to use Exchange or Google's stuff.
Exchange servers are capable of allowing IMAP access. Some also allow PO3. Some are configured to allow neither. It just depends on the server.
So - to answer your question... it sounds like you're either using POP3 (which may be deleting the email after it's downloaded it, hence preventing you getting it on any other device), or you're using IMAP and deleting it on one device (hence it's being deleted on all other's too).
With both IMAP and POP3 the emails will be downloaded to your device, but, with IMAP your emails can be deleted if they're deleted by any other device that accesses your email (webmail, PC, etc). If any other device uses POP3, it may be deleting your email before your device gets a chance to download it.
It sounds like what you want (assuming you don't want to use Exchange for some reason, why not?) is that you want to use IMAP. Any email you receive is received by your email server, NOT by your phone or PC (this is the same for POP3 too). Your phone will then connect to the email server, and update its emails and folders to be exactly the same as what is on the server, which will also be exactly the same as on your PC or any other device that accesses that account via IMAP or Exchange. IMAP or Exchange is an absolute must if you're going to be accessing your email from multiple devices, to ensure they all have the same emails on them.
Android comes with a standard email app that can handle IMAP. If I recall correctly the Desire has an improved one that comes with its SenseUI that supports better Exchange stuff. If you want a different app there are several free and paid ones, but I've never used them.