UPDATE: iPhone 3.1 does indeed fix this.
Matt Janssen has discovered what looks like a bug in iPhone 3.0 Spotlight, whereby the search feature keeps emails in the index/cache even after they've been deleted from the inbox and purged from the trash (and even obliterated from the host server). Janssen claims in the video above he's found emails he deleted several months ago using this method.
Email is likely cached to speed up searches. Initially tapping on a deleted email in a search result will launch Mobile Mail, which will promptly crash, but searching and tapping a second time will actually show the email, albeit in a buggy manner.