Is there any software that would test the reliability of a CPU? Like, check how all the instructions are working, verify that cache is not damaged, check for known CPU bugs, etc.
I've got a machine in which I suspect that the CPU might be failing, but the symptoms are weird enough that I'm not certain...
Most likely OS issue:
I would guess the most likely problem, even though you gave no symptoms, is that there is something wrong with the OS or software. I would run a Linux live cd for a while or do a fresh install, and see if you have issues.
More Likely RAM:
What makes you think it is failing? I would guess RAM or the motherboard first. I recommend memtest to check the ram.
Heat:
If you are having CPU problems, is it related to heat?
Time vs. Hardware Cost:
Is this stuff worth the time? If it is expensive, maybe it is still under warranty? If it was expensive, can you get something more powerful for cheap?
Lastly, what are these weird symptoms?
A CPU failure is very uncommon, but possible. I like to use BurnIn Test Pro to test various functionality of a system. It runs in Windows. If you want to try testing something from a boot disk, try using some of the CPU tests (like Prime95) from the Ultimate Boot CD.
You could try checking temperatures if your mobo supports it; maybe it's cooling related.
As for test software there are some things found on the Ultimate Boot CD that might help, but really if the CPU is failing you're going to get lots of quirky stuff going on that may seem totally random.
It would seem that the only way to truly test it is to get another CPU and swap it out to see what happens then. There's not too much that'll "stress test" a CPU other than just using it a lot. Otherwise symptoms could point to a bad CPU or to bad memory or poorly seated CPU/memory or something failing on the motherboard or socket...issues with these components are hard to track down, primarily because software used to test it can tell you potentially that there is a problem, but never that there's not a problem (it's like asking your brain to evaluate yourself...can't do it without bias in the perception of the brain's own state. There are plenty of cases where people ask about testing memory and various burn-in testing programs can say memory is fine but suddenly crashes go away after the module is replaced).