It seems the de-coupling is necessary, based on your findings. I would wire it according to the data sheet method though. If you look at fig 3 on the datasheet, it shows the OUT line being decoupled with a 2k resistor, but the Vdd being fed directly. What happens if you try this? It would also be worth trying with the layout in fig 4, with the capacitor and resistor in series between the OUT and "-" (GND). The suggestion to replace the capacitor between Vdd and OUT with a resistor, would mean the voltage reading on the analog input pin of the Arduino would be 5v, less some small drop depending on the current drawn by the analog pin input. The temperature output of the device would not be "seen" by the arduino.
One other point reference accuracy - put a voltmeter on the 5v pin used to feed the LM-35. You may find it is not exactly 5v, and this will distort your result. Once you know the actual level, amend aref_voltage. I suggest you make this a float as well, so you can deal with a non-integer value.
Good to see progress though!