I think I've gotten down to 8 on beginner, 35 on Medium, and... 117 on expert. My current machine shows 11, 38, and 151.
At a certain point, your hardware becomes important in determining your score [img]smile.gif[/img] Prior to that, pattern recognition is important.
I also play the dangerous way -- don't mark any mines. If you do that, when you open the last square, all the mines will fill in automatically. But if you mis-step along the way... KABOOM!