With normal power you have decoupling on the chip? It does sound like they are out of spec (are they genuine parts or clones? Were they soldered for too long causing thermal stress perhaps?)
(Also double check your caclulations - print the raw temperature value and do the conversion by hand to check)
I don't think I understand your first quetion about decoupling on the chip.
The parts I'm using are genuine dallas chips. I have the same issue with multiple chips, two were ordered last week and the other two were ordered a year or two ago. The chips are never soldered and were stored in anti-static bags.
I've tried several different codes, as I mentioned in the first post I've used the code found on the arduino playground. As well as the dallas library. They all give me the same readings. I even tried different wires and different values of pull-up resistors but no luck so far.