I'm also tempted to clean and reapply the thermal paste. I got my mac mini server on Saturday and was shocked at the 'tickover' temp and the 'load' temp. I too was seeing temps over 90C but the exhaust cooling air did not feel that hot which immediatily made me think of the themal paste.
I redid the paste on my 17" MBP CD (Not C2D) and cleared out the heatsink from fluffy stuff. That helped!
When I was turning the mini over and over working out how it all fitted together I realised that the intake for the air was only around the rim of the removeable base, it can only have been around 1 or 2mm wide, makes me wonder if that isn't a restriction to the flow. Would be interested in others thoughts.