Electronic – Strange output of Temperature probes

Have you actually measured the voltage the LM35 is outputting with a multimeter? I would trust the LM35 far more than the ATmega's ADC to go completely down to 0 V.

From the graph you included, it looks like something is hitting a rail somewhere.

If it is indeed the LM35 outputting the errant voltages, try a pulldown (~50 kilohm?) on the output to ground (or better yet, -5 V).

You're measuring a very small voltage with the built-in ADC - 20 °C is only 200 mV. Furthermore, without a negative power rail, the sensor is only really good to 2 °C, and any bias current on the output (from the ADC) will probably affect the readings you get.

Edit: there are a lot of products already on the market exactly like this if you don't want to make it yourself. Look at numbers 2 through 5: http://homecooking.about.com/od/kitchenequipmentreviews/tp/electricthermom.htm

If you can get a resonant coil and thermistor system with enough SNR to reliably detect temperature remotely, then that seems to be the best solution. If not, here's some information about wireless sensor nodes.

In terms of wireless data transmission, infrared radiation of an object increases in proportion with temperature. Unfortunately, this information could only tell us the temperature of the surface of the meat, and not the center. At first I thought maybe you could use a spike with very high thermal conductivity so that you could see the temperature of the inside by looking at the spike with a thermal camera. However, the spike would just effectively cook whatever its touching so it would probably do more harm than good. For this reason, whatever design you choose to go with, the spike you insert should have very low thermal conductivity so that it doesn't cook the meat from the inside. Unless you want that.

The IR radiation coming from the oven/pan also introduces another problem: noise. You will have to select an IR transmitter with a frequency that doesn't overlap with the IR noise from the cooking implements. Maybe all IR transmitters are designed this way anyway, I don't know. Just something to be aware of. You could use an RF transmitter instead, at the cost of higher power. RF has the advantage that it will penetrate through more obstacles than IR.

A thermoelectric generator would be the most effective way to harvest energy. Because there is expected to be a large temperature difference between the outside of the meat, and the insulated inside, you could place a TEG along this gradient. But then you probably need to have a voltage regulator circuit to power your digital control circuit, temperature sensor and transmitter. I don't know if the TEG can produce the power you would need. It may be easier to just use an energy storage element like a super capacitor or chemical battery. Here is a tiny battery that operates up to 85°C: http://www.infinitepowersolutions.com/images/stories/downloads/ips_thinergy_mec225_product_data_sheet_ds1014_v1-1_final_20110913.pdf

They say, "Standard electrochemical degradation is proportional to temperature increase. Contact IPS for performance information regarding higher temperature applications up to 150°C."