I came across this video on the weather channel site today. As you can see, at -22 degrees boiling water simply vaporizes when tossed in the air.

http://www.weather.com/outlook/videos/what-happens-to-boiling-water-at--22-19419

What would cause this?

Well, theres fog and snow involved, and You can see it in the/a naked eye.
As far as i understand, it's because water is close to gas form when boiling, and when dispersed, some of it vaporises and the rest goes into snow. Though i'm not a physicist, nor was i ever good at that, so i could be very wrong.;)

I seem to recall from science class all those years ago that the rate of evaporation is proportional to the difference in temperature so from ~100 degrees to -22 that's a lot of difference

It"s due to relative humidity. In a very cold environment, air humidity can be extremely low. So the boiling water once thrown in the air is absorbed by the air. But as the air is so cold, it instantly converts into ice powder.