If the ExposureMode is an automatic or semi-automatic one, such as A, P, S, but not M, you could reverse the Sunny 16 rule to find out if the photo has been exposed for a sunny or overcast day. By comparing the actual exposure with the exposure based on the Sunny 16 rule, you can estimate if it was sunny or not.

The lighting from the sun is close to constant, so an ideal exposure will always be the same with direct lighting.

But it will work only if the picture is more or less grey(the closer to a 18% grey card, the better). It won't work with a picture of a white patch of ice, nor with a black coal mine. But it will probably work with vegetation.

EDIT

This method will give you a lot of false negative (it's sunny, but the picture was taken in the shade, or inside), but it won't give you a lot of false positive, as there aren't many pictures of things lit by a lightsource as powerful as the sun. The main source of false positive will probably be, as MichaelT said, the fog, or maybe thin clouds.

EDIT 2

Another idea is maybe to use the white balance? But again, you will have a lot a false positive and negative. You will probably need a lot of images taken at the same place and time in order to deduce something...