I am still curious. If you have a small speaker that you can spare, you request you stick the sensor to the speaker cone and see whether the LM35 is acting still smart!! (with the speaker on or off)
Maybe your LM35 measure is sensitive to the parasites emit by the engine car, when ON.
use of screnned cable for the sensor ?
or drift of power supply ?
How do power the LM35 ?
This can be easily checked by using the dry cells for the power source. Also, the spark plugs (if it is a petrol engine) carry high voltages and some of that can easily be picked up...