Asus notebook screen turning black and freezing randomly.

I have a 2.5 year old Asus N81vp laptop with 4 GB RAM (2x 2 GB) and 1 GB ATI 4650 discrete Graphics card. I am on Windows 7 Profession Edition. For the past 6 months (started just around last few days of 2-year warranty) this laptop is crashing infrequently. I am not running any games on this laptop. The crash/freeze happens randomly when I am playing a flash video or using google maps in chrome or simply switching between windows.

When the "freeze" happens, I get a black screen and the fan starts spinning at high speed. Connecting to an external monitor then does not give any output. Only hard-reboot gets the display back.

So far I have tried these options
- Re-installing AMD/ATI graphics card drivers (I already have latest version)
- Uninstalling graphics card drivers
- Using one RAM at a time (This didn't help anything because the issue seems to be intermittent)
- Ran memtest (test passed without any issues)
- Reinstalled windows from scratch
- Replaced the graphics card with a new one of the exact same model (the problem still exists to my horror).

The only significant progress I made in the last one month of troubleshooting is that I can reproduce the "freeze" on-demand by running HDR/SM3.0 test on 3DMark06. SM2.0 Graphics test and CPU Test run perfectly fine.

I contacted Asus (I am out of warranty) and they asked me to ship it to them. My previous RMA experience with them has not been that great so I decided if the problem is severe then I'd just buy a new laptop. But first I want to find out what/where the problem is. Can anyone help me?

Any suggestions anybody? I have monitored the GPU temperature for a while, and it is normal (45 - 53 C).