Corrupt desktop?

I've had this problem for atleast 6 months and I've yet to figure out the cause or why the issue comes and goes for no apparent reason.

When booting up Windows (XP w/sp2), one of several things will occur followed by the screen turning black and I'm unable to reboot with ctrl-alt-del. Windows boots into Safe Mode fine.

1. A portion of the icons will display...one being only half there...
2. The icons are all there, taskbar is fine, background tasks load and everything is good until I interact: move and icon, display a popup balloon, or launch a program.
3. Sometimes it skips the above and goes straight to the black screen.

I've tried:

Uninstalling/reinstalling: Video drivers, Catalyst drivers and DirectX
Restoring from various restore points
Deleting all restore points (in case there is corruption)
Cleaning out dead files
Cleaning registry
Run anti-virus/trojan software (Norton's, Panda and Ewido).
Defragging the drives (in case there was file corruption due to fragmentation)
Reset BIOS to default settings (I generally tweak settings for performance)
Pulled the video card, cleaned it, check the fan and reseated it
Underclocking the GPU
Uninstall/reinstall Microsoft's .net 2.0 framework
Had Windows try it's self-repair
Replaced a faulty power supply - voltages are spot-on now

Pulled RAM (because I also sometimes get a BIOS error (3 short beeps) that indicates video card or RAM issue. Ran Memtest (no problems). However this issue like the Windows problem comes and goes. Usually the BIOS problem disappears once the components have had time to warm and a cold-boot is done (possible cause ..micro-fractures?).

The black screen most often occurs either at #1 above or after everything has loaded and the video card does a refresh/restore at the tail end of a standard boot.

I don't have spare parts to swap components. Is there any diagnostic software that might help in tracking fown the root of this issue? Is there any way to test for micro-fractures in components (other than swap parts)? Any help would be appreciated.