I wouldn't worry about it, if you have a good fan (which you do), any themal paste (again, you do), and good airflow (you now do), then I would say it is safe and your MB sensors are wrong. When you said temp jumped 10C, I had a feeling that the sensors may be bad. With a big HS like that, temp jumps should be in the 1-2C range. Even a hot processor can't heat a big block of metal that fast.
Of couse, you can try the other thermal paste just to see if you can lower the temps, but I doubt it will do anything.