dedupe shows non-existant contacts

While deduping, I decided that one of the contacts (a dupe) wasn't worth merging, so I just deleted him. To my surprise, he still shows up on the dedupe results. So then I went back and deleted him permanently. Nope, he's still there. Then I tried merging some other contacts to see if that would flush the cache. Again, that pesky nonexistant contact still shows up in the dedupe results when I run it. (but now of course I get a fatal error if I click on merge for that record, since he doesn't actually exist)