What type of brakes is least subject to failure in the winter? There is a lot of snow in the winter where I live. Different kinds of snow; soft, sticky, wet, etc. And ice too. It can get pretty cold: -25 °C (-15 °F). We drop salt, sand and gravel on our roads.

I'm about to buy a bike that I'll be using this winter for commuting to work. What kind of brake will work best in all kinds of wet and icy situations?

I'm interested in braking performance as much as long-term durability.
Like the other answers, disc brakes are the only way to go if you plan on your brakes getting wet at all. After riding disc brakes for a while now, I will never go back, even in good conditions. I would also really recommend hydraulic disc brakes over mechanical ones, especially in poor conditions. With hydraulic brakes, you don't have to pull as hard to get the same amount of stopping power.