Are deleted emails really deleted?

In short: maybe.

First, let's be clear: when you delete a file in many email programs they're actually moved to a recycle bin so you can often find them there until the recycle bin is emptied. When you empty the recycle bin, then the messages are actually deleted.

The problem is that different email programs all use different approaches to storing their email. As a result, there's no one answer as to what happens when they delete a message.

One clue is if the email program provides a "compact" function for its email storage. That implies that the file will grow as email arrives, but when files are deleted the file doesn't get smaller until you compact. That implies that like a file system, messages that are deleted are simply marked without freeing up the space immediately. Like file systems, as long as new messages haven't overwritten where the deleted messages used to be, then it might be possible to actually retrieve deleted messages. It might need special tools, but it could be possible.

One caution is that some email programs automatically rewrite or compact their files on exit, so this might only work if you make a copy of the email files before exiting the program.

And finally, all of this applies to email that's downloaded to your system. Web-based email like Hotmail or Yahoo, server-based email systems like Microsoft Exchange, or IMAP servers add another level of complexity that makes deleted email that much less likely to be retrievable.