Your motherboard is a socket 775 board with an Intel 915P chipset. It supports pretty much any 90nm, 800mhz FSB, P4. The only one available at Ebuyer for your board is the P4 541 3.2ghz (your current CPU is a P4 550 3.4ghz)
http://www.ebuyer.com/product/142970
I would still lean more toward the motherboard than the CPU. The CPU has a thermal trip point at which it will just shutdown.
You should see if you can test the CPU in friends system prior to buying a replacement CPU, or have it tested at a repair shop.
As for cleaning the TIM off the CPU and heatsink, rubbing alcohol works pretty well if you don't want to buy something like the cleaning solution mentioned above.