Well, in my case, the problem seems to be completely resolved. It ended up that I just bought a new video card (a cheap GT210) for the time being. My system has stayed up almost 24 hours with no significant issues.
It seems that other issues mentioned in this post are using a variety of hardware. So, to try and isolate those types of issues, I would suggest grabbing gtkperf or just running glxgears for a few minutes to an hour to check if you are having GPU problems like mine. This basically takes the problem outside of XBMC's domain and helps to confirm its caused by other factors. These tools might not be stressing the GPU enough, but they might give you an idea if that is a direction to pursue.
You can also try doing some physical checks. If you open your case, and you note significant heat sources, then that might help to pinpoint possible issues. I'm not saying warm... the hardware will likely have a bit of heat, but if you inspect the system (while turned off) after a failure and there are components that are very hot to the touch, that's suspicious. Its also helpful to physically look to make sure fans are turning, etc. General areas to look: CPU & fan, this should be fairly cool. South bridge (usually has a sink or a fan)... if you have a fan, make sure its turning. It might be warm, but not hot to the touch. Lastly GPU... if you have an all-in-one MB, this should be a separate heat sink or might be built into the south bridge.
The lm-sensors package might give you a good idea how hot its running while you're in xbmc. It should be a good indicator of problems, but was not conclusive in my case. This is a decent guide for that:
https://help.ubuntu.com/community/SensorInstallHowto
In the case of heat issues with hardware, this seems random because you are waiting for a threshhold that the heat must reach before the failure occurs. However, stressing the GPU or CPU to failure should be simple in these case: In the case of the GPU, if you use VDPAU, then simply find a high bit rate H264 movie and play it. If you have some sort of graphics benchmark, that also should work. There are some episodes in the Planet Earth series that have high rates, but they are not usually sustained. There may actually be test files online that may help with this. It should fail fairly quickly if there is a GPU issue. If you suspect CPU issues, then turn VDPAU off and play the same movie. Memory is also suspect to heating issues, but this usually only happens if you are over clocking. However, faulty RAM can cause a wide variety of weird and random problems.
From a software side, the key is reproducing the error in some generally expected way. If it seems to fail in some circumstances "randomly", try finding a situation where it always fails. Generally though, in my experience, random software crashes are fairly rare unless there is a weird memory leak. I should have realized this from the beginning of my testing. These random issues usually indicate a piece of hardware is flaking out.