Notification Center on iOS 6 is not removing deleted emails
This is a bug that should be fixed, but possibly also a feature request.

The problem is simple. iOS won't remove notification from notification center when the app that post the notification launches. The developer has to tell the app to do it in order to clear all notification at app launch.

While this behavior is expected by user, developer might want finer control over when to clear the notification.

So, Mail doesn't clear the notification, and posted notification cannot be removed by app. And that ultimately result in this weird notification that links to a deleted email.

You should file a bug at Apple Bug Reporter.