My thinkpad T43p (pre lenovo) can play supreme commander with the settings set to minimum, and plays at 20 fps until more than about 400 units are in game. XD
Oh, First person shooters... UT2k4 max settings. I know its not much of a stress test, but the laptop is still 3 years old. =)
The only thing I can suggest when looking for a laptop that can do some gaming, make sure the Videocard has its own discrete memory, ie the videocard doesn't share its memory with the rest of the system. It will help a lot.
As mentioned, Desktops are a lot easier to upgrade, and also they are a lot better with disapating heat, which can help with performance, and help let your equipment last a little longer (heat, the #1 enemy of engines, as well as the most common enemy of computers for that matter).