I would definitely recommend the DS18B20 Temp sensors - i have a system very similar to what you describe but completely built using the PICAXE range of microprocessors. I have just undertaken to move this to the Arduino environment.
I have been using the DS18B20 Temp sensors for about 5 years now and they have been brilliant - i have had two failures (from poorly built waterproof housings that i made) out of 12 units in 5 years.
Their accuracy is outstanding. If you are worried about them - then deploy two in each location and sanity check the readings from both against each other and create a weighted average.
Craig