Arduino LM35DZ giving incorrect voltage
I don't have an answer for your question, but I'll write down what I could tell from your setup.

In spite of the low quality of your second picture, with a bit of hard work (and maybe some faith), I can tell that your connections are correct: 


The gray/orange/brown wire goes from \$5V\$ to \$+V_S\$;
The gray/blue wire goes from \$A0\$ to \$V_{OUT}\$;
The gray wire with large black stripes goes from \$GND\$ to \$GND\$.




The LM35DZ (datasheet) output follows the formula below:

$$V_{out} = 0 mV + 10.0 mV/°C$$

That means you'll get the following results, approximately:

 Temp |  Vout
  0°C |    0mV
 10°C |  100mV
 50°C |  500mV
100°C | 1000mV


So, right there, there seems to be a problem with your setup. I can't explain why you're getting LM35DZ output voltages above 1V (100°C). There's got to be something in your hardware, but I don't know what it is.

Just to check: did you configure your \$A0\$ pin to input? It's a long shot because that may already be the default, and also because the analogRead() call probably does that for you.

Another thing to try: if you heat up the sensor a few degrees by holding the TO92 case with your fingers for a few seconds, do you get a small increase in the \$V_{OUT}\$ voltage? If so, maybe that means the batch of LM35 you got is miscalibrated. If that's the case, you may be able to compensate for that and calibrate them yourself, by adjusting the temperature formula in your code. There's some information on how to do it in the related question, How to calibrate a temperature sensor. 

That's cheating, admittedly, but who cares as long as it works? We're Engineers, not Scientists :D

Finally, I would suggest you to isolate the variables: remove the Arduino board from the setup and power the LM35DZ separately on the breadboard. Watch out for the \$+V_S\$ absolute maximum of 35V. Then measure \$V_{OUT}\$ again. If you get the same 4.16V, then the problem is with the sensor. If you get something around 300mV, then the problem is related to your Arduino board.