Sometimes, on very cold and windy days, I occasionally have trouble breathing. When a gust of cold, cold air hits me in the face, I find that sometimes my throat just won't open up -- I think there's some sort of reflex that causes this. Anyway, I've done some riding with a balaclava or fleece scarf, but I find that these can restrict the airflow and prevent me from getting enough oxygen. They also tend to direct the air up into my face, fogging my glasses.
How do you deal with breathing in extreme cold?