If your thermal paste is dry, it probably won't make good thermal contact. I'd try replacing with fresh paste to see if that helps. The purpose of the paste is to fill the tiny crevaces and imprefections on the surface of the heatsink. Unless the heatsink is really warped, machining it won't do much for you. Cheaper to buy a bigger 'sink.

But 63C doesn't sound too bad.