Have you tried simply raising the ground of the LM 35 by placing a diode in series with the 0 terminal?

That way you might just add a single 10ct component and get rid of the problem completely.

Just enough to raise the ground of the LM35 above the input sensitivity threshold.

One Si diode would probably work, two Ge in series would be slightly better (because you get more range).

So that would be:

          +
          |
          |
      +---+--+
      | lm35 +---- out
      +---+--+
          |
         ---
         \ /
          v
         ---
          | 
          |
       ---+-- gnd

The diode is 'up side down', you simply use the voltage drop to raise the 0 of the lm35 (like a zener diode), it doesn't know any better and will add the output voltage to the ~0.6 V the diode provides.

What happens to the voltage across the diode when the temperature changes? Looks to me like you've just replaced a calibrated temp sensor with two sensors in series!

The temperature of the diode will change right along with the temperature of all the other hardware, it's not as though you'll go out of your way to get the diode heated up.

The way it's drawn is not the way it is built, the diode would normally sit near the computer end of things, not right on top of the sensor.

The thermal drift of the other circuit is at least as large as that of a diode at room temperature, probably a whole lot larger.