After my transition from Mail.app to Thunderbird today, I discovered that quite a few messages that I had deleted long ago in Mail.app had reappeared in Thunderbird. Here's my theory of how it happened and how people using Mail.app can be sure that they're not wasting a lot of hard drive space on deleted messages.

Mail.app keeps each message in its own ".emlx" file in a "Messages" folder associated with the mailbox its in. However, simply copying an emlx file to that folder will not make it appear in the mailbox--it also has to be referenced from the mailbox's index file. So I'm guessing that what's happening is that when messages are deleted, Mail.app sometimes deletes them from the index, but fails to delete the file. So there it sits forever.

I don't use Mail.app anymore as of today, so I haven't bothered trying this, but here's how I'd try fixing it. Create a new folder and move all the messages from another folder into it (from within Mail.app). Then go to the folder you just emptied in the Finder (from your user directory, look in Library/Mail/...and find the folder from there). Look in the "Messages" folder inside its ".mbox" folder. If there are any files in there, they're orphaned messages. If you're paranoid, open them in a text editor or something to make sure they're not something you want to keep. But given that they're sitting in a folder that Mail.app thinks is empty, I think you're going to be safe assuming that they're files you've deleted (...unless you've been mysteriously losing messages that you didn't delete!)

Once you're confident that you don't need those files anymore, delete them (from within the Finder), and then in Mail.app, move the messages from your temporary folder back to the folder where you were keeping them and repeat with some other folder.