I was in the same situation as you a few weeks ago and went with the Toshiba P750-BT4G22:
http/www.toshibadirect.com/td/b2c/cdetland.to?poid=2000016420
Every other week it goes up in price by about $100 from its current price and in every other week from that it goes back down to its current $769 base price. It comes with a GeForce GT540m, a mid-range laptop GPU, an i7-2670qm, an all-around fast laptop processor, and 8 GBs of RAM for no additional cost. I've been testing it out for almost a week, since I obtained it myself, and it's a fantastic overall laptop. The screen resolution (1366x768) isn't too great, but it's good (and it's not as though gaming laptops in the price range generally do well at higher resolutions anyway), the laptop is pretty good at anything I ever need to do, and though its gaming capabilities are (understandably) not amazing, it's well-cooled for a laptop (unlike other budget gaming laptops, i.e. anything Acer) it's fast enough that it can run most things playably (25-30 fps minimum), at one setting or another, it's sharp-looking, and it's overall a fantastic laptop. I recommend upgrading to a 7200rpm HDD, regardless of size, and the backlit keyboard for an additional ~$40 total to really see the laptop's potential. In the price range ($800), you won't find much better. A drawback might be the somewhat short battery life, assuming you only buy the base battery model available, but with eco mode on, it'll last ~5 hours while just typing, according to my battery icon's estimates and an additional battery can always be bought later if necessary.
My own tests show that is certainly outdoes either current-gen "serious" console, if that reference point means anything, and will max out BioShock (at native resolution, with V-sync, and without forced global lighting) at a good 55-60 fps during most gameplay with drops to about 48/49 while under great stress, the first Witcher on max settings with 2xAA at roughly 40-50 fps, Mount and Blade: Warband on max everything with Vsync and 8xAA at 40-60 fps unless in the middle of a large battle, it'' blow Minecraft out of the park with, far and beyond, higher than 60 fps regardless of what you do, and really just about any game from 2007 and below with 45-60 fps depending on game/if you go crazy like me and apply 8xAA with unnecessarily high-detail shadows
P) and it can play mostly anything up to 2010 reasonably well (30-40 fps doable with medium-ish settings). Though I haven't tried it myself, I hear it can also run modern games such as Skyrim (expect about 30-ish fps on a mix of low and medium settings, reportedly). Anyway, it's a decent card and the laptop itself is overall a pretty good deal for the price which I'm very happy with. Here's some more information on the GT 540m, the GPU itself:
http/www.notebookcheck.net/NVIDIA-GeForce-GT-540M.41715.0.html
Edit: Though the things I've noticed can vary a decent but from what's been said on that site I linked. Their approximation for Just Cause 2 is way off, for example... this laptop definitely runs Just Cause 2 well, from my experience, and Risen/Metro 2033 don't run quite as fast for me as they say there, though I'm not sure which resolutions they're playing at which makes a difference. Also, the 650m mentioned in an above post is faster and though the 540m is decent, its weaknesses guarantee that it doesn't have much lastability, but with an $800 budget, you're going to be making some compromises with GPUs stronger than about a 540m. I'm personally skeptical of the above HP laptop because for the price and specs, I'm willing to bet it's not the most reliable laptop, as in it's not going to the best-cooled. That's just my gut feeling, as it's a business model both Acer and HP have a reputation of doing, and the HDD on that thing is probably 5400rpm, which is a bit slower. It's almost too good to be true, basically, is what I'm thinking, but as far as pure specs go, it's a steal for the price. Oh, and yes, Alienware is an overpriced brand that charges extra simply for being Alienware. In addition, Sony also tend to overcharge for their laptops. HP and Acer tend to cut corners in order to provide a competitive price for given specs. Asus and Toshiba are in a nice sweetspot, currently, where they tend to provide really good value for the price while maintaining reliability, in my opinion. Of course, there are exceptions to everything.