First, what TIM (thermal paste) are you using? Have you checked it lately? If it is old and dried out, you need to clean it out and refresh it. If it is the stock interface material, you should never have been using it in the first place. Arctic Silver 5 is the standard for overclockers, there may be better (and more expensive) but you won't go wrong with AS5.
Second, what verification software are you using? Does your system pass Prime95 (for example) before crashing?
Third, if you are using the stock Intel fan and cooler, you are doing it wrong. Nothing besides very modest overclocks should be attempted with stock coolers.
Is 2000 RPM the normal speed of the Intel fan or is my fan somehow broken
(which could explain the overheating).
In this case, any recommendation for a
good fan for OCing ?
Yes, 2000 RPM is a common speed, but it more up to your Motherboard what speed will be maintained than the cooler. Megahelams is the current standard for overclockers, but it is very large and a little expensive. The Corsair H50 self-contained liquid cooler is another option.
Hypothesis I fear is the right one: can the CPU have been slowly damaged
over time by this OCing, meaning there
is nothing much to do except waiting
for it to die ?
Spontaneous reboot/crash may be the motherboard saving itself from heat. CPU 95C under load is doable but really pushing it, especially for long term operation. You may have damaged something, or lowered the OC thresholds. The damage may be the Northbridge or RAM instead of the CPU. But, I'm thinking running at 95C is just too hot for your cooling solution. What are your Motherboard temps?
(As a side note, I am surprised that
the 9550 is still around 300 $CDN
here... Thought it would have been
cheaper with all those i3/i5/i7
The price of the 9550 is a product of supply and demand. Intel is phasing out Core 2 era CPU's, the 9550 is rather high-end and still in production, so high demand from (a large number of) upgraders and a limited supply means vendors can charge what the market will bear. MicroCenter was charging $169 recently, current $179 for Q9550 proves that Intel is not the price gouger here. Unfortunately, you gotta pick it up in store to get this price.
The final answer is this, you may have a damaged CPU, north bridge, ram, or maybe just dried up TIM or a crooked fan mount or just too much dust built up past a heat threshold. How much extra air are you getting into the case? How many input fans are you running? How many extra output fans have you added? Size and RPM? Healthy overclocks require Big Air.