To start with, here is my system.

ASUS K8N4-E DELUXE ATX AMD Motherboard
AMD Athlon 64 3700+ ClawHammer
ATI 100-435513 Radeon X800XL Video Card
1 GB Corsair RAM
Microsoft Windows XP
Sony IDE DVD Burner Drive
Samsung Spinpoint 160 GB HD
AG II 480 W Power Supply
Envision 17'' CRT monitor

The problems:

1. Sometimes, the monitor fails to recognize the computer (Standby light comes on, and all computer fans etc. turn on, but nothing appears on monitor), and it an audio message says "System failed VGA test."
2. Computer freezes randomly. (Sound cuts out, video freezes, Ctrl-Alt-Del does nothing. I have to restart the comp.) This usually happens when running a program I have just installed, but not always.

My futile attempts at solving the problem:

1. Purchased new memory. (Formerly 2x512 MB Kingston ValueRam)
2. Updated windows and Vid card drivers. No effect.
3. Tried with different monitor. Did not get "System failed VGA test" message in 5 boots, but monitor lost connection with computer after about 10 minutes.
4. Removed power from 2 case fans(Thinking problem might be overdrain on PSU) System still froze.
4. Despaired and took it to local comp repair shop. They installed a new power supply (formerly 500 W OKIA) and another fan. They said that they ran BurnWizard and other programs for hours without a single freeze, and they never had any problems with monitor connection, despite the fact that they were using an older and crappier monitor than my Envision (Had no problems with both power supplies, mind you.). To be honest, this only made the problem more perplexing, since the only thing over there that was different than at my home was the monitor.

Any ideas? The other monitor that I tried at home was missing a pin and is kind of old (1999/2000), but it runs my parent's comp (from around the same year) without any problems. Thought it might be the video card, except that they reported no problems at the shop. It shouldn't be overheating, because I have 4 fans (including one very good CPU fan), and the temp is reading under 30 C consistently. Any advice would be very helpful.

UK

run a video card diag, 3d benchmark , this should stress even your x-series vid.

http://www.futuremark.com/download/?3dmark05.shtml

this is the url for the trial version.
heat likely isnt an issue, if it craps out on post.
the other variable btw between you and the local shop is power from your wall.
do you have a ups? if so, does it have the power to boot your system properly?
try another plug, on an other circuit of course.
let me know how 3d bench made out

5048 was my "score", according to the program. It did not freeze.

What do you mean by UPS?

Uninteruptable Power Supply, battery backup

No.

have you tried another circut? another plug in?

Yes, but lots of outlets in my house are bad. I will try it at college and see if that helps.