You can get cheap Alienware M5700 laptops now on ebay with Nvidia 6800 GPUs in them for about £300/$500 if you don't mind XP
Other ones to look out for on the edge of your price range (£450/$700) are Asus G1 (Nvidia 8600GT), Dell XPS 1710 (Nvidia 7900GS/GT), Acer Gemstone G (ATI 4570 - Nvidia 9600GT) used/referbished.
I recently picked up a refurbished Fujitsu Amilo 3553 with ATI 3470x2 cost me £300/$500 plays Battlefield 2 and 2142 smooth as silk at 800x600 in Vista
All gaming laptops will have to be plugged in to game, batteries won't last very long with the CPU and GPU going full pelt IMHO
DinoHunter (still no nVidia compo voucher!), CPU/GPU Benchmark, DarkFish Encryption DLL, War MMOG (WIP), 3D Model Viewer