Note that IMAP clients typically default to not actually permanently deleting an email message until you tell it to by issuing the 'Expunge' command. Most of the time the message is moved to a folder on the server (Trash or Deleted Messages or something) or marked for deletion (and can be undeleted).
I suspect your message is not completely gone and is still on the server in either a Trash mail folder or marked for deletion and ready to be undeleted.
POP is actually more destructive because there is only one copy of the message ever and if you delete it, there is no likely to not be a backup on the server. It is simpler to understand and use however and many people prefer it.
- DreamHost Head Honcho/Founder