As of February 23, 2003, the Windows Minesweeper world records* (as recorded by http://www.metanoodle.com/minesweeper) were as follows:
Beginner: 1 second, held tied by at least 33 people. This is basically luck. You click once or maybe twice within the first second of play, and just by luck, all of the mineless tiles are uncovered by these clicks. Unless your reaction time is really good there is really no skill involved. 2 seconds, on the other hand, can very much be a matter of skill. One good 2-second video recorded by Damien Moore had him clicking once, then, within the space of one and a half seconds, noticing AND CLICKING on the only two other positions on the board that needed uncovering. To spot these within the time requires great skill, not fluke. Note: 1 second is the minimum possible time for a Minesweeper game. The timer hits 001 immediately after releasing your first click and before the game ends.
Intermediate: 10 seconds, held by Matt McGinley. The way to win the game is not by marking all the mines (which would take at least 20 seconds even for a skilled player), but by uncovering all the tiles which DON'T conceal mines. In this run, McGinley uses the technique to the full to blaze across the board, clicking only where he needs to. He starts off with a relatively big (and relatively lucky, i.e. minimal additional clicking required to isolate all the mines) reveal, follows up soon after with another, smaller reveal, then finishes before you can blink an eye. ...and he made an error. AN ERROR. He could've made 9 seconds. Maybe even 8.
Expert: 43 seconds, held by Lasse Nyholm. Stunning. Just stunning. The man purrs across an Expert board at the same rate as I would traverse Beginner. Requiring incredibly fast mental dexterity, pattern-recognition instinct, lightning-fast logical reasoning and a super-accurate mouse finger, this is the definitive Minesweeper video. It's difficult to imagine how a man can think and act so fast until you witness it. One to amaze your friends with. All skill, no luck.
All these records have video proof, available here: http://www.metanoodle.com/minesweeper/videos.html. You will also need to download a relevant codec, this is explained on the video page.
Humbling, is it not? Proof that regardless of how good you think you are, there's always someone out there who can wipe the floor with you.
My records are 5/43/196. *sigh*
If you want to record your own Minesweeper achievements, the best way to do so is by downloading the Camtasia screen-capturing application from http://www.techsmith.com/defaultflash.asp.
* It's possible that these are not the actual fastest recorded times, but very, very unlikely. It's near-inconceivable that an individual would have honed his skills to exceed those of the record holders, without the incentive of a whole planet of fellow players to drive him on.