I've been having the same problem with deleted emails showing up in Spotlight on iOS 6.0.2 (iPhone 5) so I did some experiments. (I'm using an IMAP account, not POP, and all my folders are on the server.)
There are actually two different problems (three if you count people who don't check all their account folders so the message is just tucked away in a place they didn't think to look).
The first problem occurs when you compose a message but don't hit Send, then hit Cancel, hit Save Draft, go back to the draft, and send it. Then you go to the Sent folder and delete the message and go to the Trash and delete it there. Now it doesn't show up anywhere in any account folder. But, if you go to Spotlight and search for something in the message, it will appear and you can bring it up and send it again. Mail is obviously squirreling away the draft in a place where it can't be deleted. Nothing short of a backup, reset, and restore will get rid of it.
The second problem occurs when you delete a message from a folder and then go the Trash and delete it there. If you immediately go to Spotlight, you'll see a "ghost" message: it's in Spotlight but if you try to bring it up, you'll find it doesn't really exist and Mail either shows a blank message or shows the account folders. You can get rid of these "ghosts": press the Home button to see the home screen and then double-click the Home button to show the running apps, then press and hold on the Mail icon and click the '-' badge to quit Mail. Then if you go back to Spotlight and search again, they're gone.
So there are two bugs: one serious and one that can be fixed by quitting Mail. And these are caused by real files being kept by Mail so using iErase or Zero Free Space to clear free space (by writing a huge file) has no effect. And, until Apple fixes the serious bug, never, ever, save a draft. (And if you do, you'll have to back up, reset, and restore.)
