CPU Temp & Fan Speed

[#1]

My wife's PC auto-turned off yetserday and repeatedly rebooted sometimes after entering windows but usually just before. I supected either a virus or overheating so set about checking the CPU fan, etc.
The fan was clogged with dust and, after a little TLC, was spinning once more.. A cold boot into BIOS showed the CPU at 41C with the  fan speed at around 2200rpm.
I gave the PC a heavy video render for about 10 minutes then powered down and back into BIOS and the CPU was at 57C with the fan speed at around 2500rm.
I left the PC in BIOS while watching the temp which slowly reduced to 50C and the fan speed to under 2000rpm where the temp crept back up again. The temp has remained at 58/59C with the fan speed at ranging from 2300 to 4100rpm (system temp is 20C).
My PC (Athlon 64x2 6400+) not under load but with windows running shows a CPU of 41C and fan speed of around 2700rpm.
My wife's PC contains an Intel Pentium 4 3GHz.
My questions are:
Is the CPU temp of 58C while only running BIOS indicative of a possible impending failure or can I assume it is 'normal'?
Is there a free util avaiable to contuniously monitor temp/fan in Windows (my software came with the Asus MB).
Thanks

[#2]

Easy one first Speedfan should do what you want http://www.almico.com/speedfan.php
I am not familiar with that processor and the standard heat sink but I suspect that having hit the over temperature limit the thermal interface material may be a bit shot and could do with replacing.
However the good news is that that processor has always run too hot so the temperatures you are seeing are not completely out of the ordinary. It does sound as though the bios is controlling the temperature to about 50 deg C

[#3]

Intel cpu'srun hotter in general than AMD's and from memory pentium 4's run hotter than most.  Cleaning the fan helps but if the fan is clogged then a general pc clean is in order and checking the heatsink and its paste is still viable

[#4]

^ Yep P4's were one hot chip. That's why they have coolers the size of breeze blocks
Just powered up ASUS Utilities and it reports my AMD CPU at 24degs and the fan speed around 3391rpm.
2200rpm does sound a little slow for a P4. See if you can take the fan off the heat-sink and check that there's no dust or fluff got tangled in the bearing.

[#5]

I got a Celeron D that happily hits 56C. I was rather shocked initially but came to accept it. The only reason it doesn't get used now it because the PSU is noisy so it just sits next to my main PC as backup.