For temps from 34F down to -20F (the coldest ride I ever took), I use 1 pair of heavy wool socks, a neoprene overboot, Sidi Dominator 5, and Hotronic electric insoles with the M4 (high capacity) battery. For temps -20F to about 10F, I use a sock rated for -30F. Any warmer and that sock is uncomfortably warm. The electric insoles are not warm, per se. Instead, the Hotronics kick out just enough heat to prevent the body from cutting off the blood supply. This combo has held me for as long as two and half hours. At the end of those rides, my toes were lacking pain and numbness and the rest of my foot was sweaty and warm.
I also used a piece of aluminized (shiny) mylar below my insole. This has helped, but the minor friction wore off the coating before too long, and negated the benefit.
There is a lot of talk elsewhere about switching to a platform pedal, but I like my cleats. I find that the plastic body of the Speedplay Frog helps prevent the cleat from becoming as much of a heatsink as an SPD cleat.