It is the grease, it makes the heat transfer from CPU to HSF much better, the dramatic drop in the temperature shows you why it is a *must*. You're really lucky you didn't burn that CPU of yours!
Otherwise, I have same problem as you, idle temps about 55 degrees centigrade, case 35 degrees...