Getting a laptop with good dedicated graphics for under $1000 is a difficult task. Your options are extremely limited, and I highly doubt you will find one with 512MB within your budget. A DV6500T or DV9500T as you suggested would be candidates, but they have low end 8400M GS and 8600M GS graphics.
Another option is the Dell Vostro (either Vostro 1500 or Vostro 1700), but it's obviously not available in store. You can get a Vostro with an 8600M GT which is far superior to an 8600M GS that HP's come with. What you will be sacrificing is style, since the Vostro is a business notebook and is plain black (which in my opinion looks nice and refined, but not as wowing as HP). But they are very good deals considering you can have one with 8600M GT graphics, a C2D, and 2GB RAM for under $1000.
So I would suggest your best bet is the Dell Vostro 1500 or 1700. I would opt for minimal RAM (choose 1GB and buy an upgrade aftermarket and install it yourself), and take your savings (probably about $50) and put that toward the best processor you can afford. If you want to stay under $1000, that will probably mean a T5470, which is a budget dual core processor, but a solid performer for its price.
I built the following system and managed to stay under-budget:
Dell Vostro 1500
-Core 2 Duo T5470 (1.6GHz, 2MB L2 Cache, 800MHz FSB)
-Windows Vista Home Basic
-15.4" WXGA with TrueLife
-1GB DDR2 RAM
-80GB 5400RPM HDD
-8x DL DVD+/-RW
-256MB GeForce 8600M GT
-802.11g WLAN
Total: $888 (I would then take my savings and buy 2GB RAM at NewEgg), bringing the final cost to roughly $1000. Since Dell doesn't offer 7200RPM drives, I would stick with the basic 80GB 5400RPM SATA HDD for now, and when you get enough money, invest in a good sized 7200RPM SATA drive later. You can opt to build one with a large drive through Dell, but it will be expensive (blowing your budget), and it will be slow (5400RPM).
Hope this helps.