When the temperature is changing from, say 72 degrees to 73 degrees or from 74 to 73 degrees I would expect it would take some time for the epoxy casing to heat/cool through to where the sensor is actually sensing. The datasheet indicates a conversion time of .1 - .75 seconds; are you allowing adequate time for the temperature change to propagate? Even as the sensor continues in the "correct" direction, there must be some lag between the actual temperature and the sensing element.
If it is truly a hardware issue - and it requires a read/ write or some other electronic trigger to affect the suspect reading - then the problem should persist over several seconds or minutes. If you read say... once a minute... does the problem remain? What if you change the temperature rapidly - perhaps using "freeze spray" - to speed the temperature change of the body of the sensor, does this effect your results?
Bookmarks