maxwellperfect Interesting question, and one that, perhaps, depends on what we mean by "mystery." (I've tried to tackle the subject in my "Favorite Mystery Films" thread, and it's a doozy, let me tell ya!)
I'm trying to wrack my brain to see if I've seen a single great puzzle-plot movie since
The Last of Sheila ('73), which I highly recommend.
Perhaps
Zero Effect ('98)? Interesting little independent movie but with some big stars: Bill Pullman as the Holmesian Daryl Zero and Ben Stiller as his not-so-loyal "Watson." I didn't find the plot all that surprising, but it's got some of the best clues I've seen in a cinematic mystery.
Speaking of great clues,
The Prestige is not a mystery but acts like one: the cluing is audacious and brilliant, and the plot delightfully surprising. My vote for Nolan's best picture, by far.
Ditto for
The Illusionist. Less well-clued than
The Prestige, perhaps, but more of a mystery, with a brilliant variation on an old gimmick invented (as far as I know) by Israel Zangwill.
One blog I follow recommends (of all things)
Harry Potter and the Goblet of Fire and
The Simpsons' "Who Shot Mr. Burns?" as great mysteries. After some thought, I agree with Rich (the blog owner) on the subject. Excellent cluing and fair-play, surprising plots in what are (for mysteries) unusual settings,
Hope that helps a bit!