Heat Factory (www.heatfactory.com) makes insoles that take small heat packs that fit in a slot in the sole under the ball of your foot. I've used a pair in ski boots and they stay hot for about 6-8 hours in moderate temps. When you don't need the heat pack, a piece of foam fits into the slot. You'll see how they work on the website. The downside is that when the pack first heats up, it is almost too hot, so your foot might sweat a bit, but then again, I was wearing them in plastic boots, so that probably made a difference.

For sub-freezing temps, mukluks seem popular. Steger makes them (www.stegermukluks.com). Empire Canvas Works (www.empirecanvasworks.com) makes a boot that is somewhat like a mukluk. Neither one is waterproof, so only really good for below freezing. The idea with a mukluk is that they are flexible, so you have good circulation to your feet. The Stegers have removeable felt insoles and the ECW boots also have removeable liners.

You could also get the insulated NEOS overboots, which I think have already been mentioned.

I've snowshoed with Sorels, but mine were a bit big, so don't know what hiking a long way in a good fitting pair would be like.