How much approximate power is dissipated on these heatsinks?
Unless it's very small, the DS18B20's epoxied (with a good sized blob, clean/abrade the surface first) should be fine.
I would suggest running the leads and the first 1-2 cm of the attached leads in the epoxy too, so the small amount of heat conducted away by the leads would be insignificant.
You also COULD use pre-packaged DS18B20's like these: http://arduino-direct.com/sunshop/index.php?l=product_detail&p=151
You could even attach those with a metal U-shaped strap and some heatsink grease, and be able to more/remove them.
DISCLAIMER: Mentioned stuff from my own shop...