Why do MV lamps have trouble starting in cold weather? And when they do start, they don't get as bright as normal.

I'm not sure.  I know from first hand experience that it can vary from manufacturer to manufacturer.  I have an older GE and GTE Sylvania at home that would start like champs even at -40° but a Philips Lifeguard, Regent and Caster bulbs that refuse to start at -15°F.  However, once lit they all seemed to reach full brightness with no problems.

I thought the light output of high-pressure lamps is not dependent on ambient temperature (within "normal" limits) because the arctube burns so hot that it's not influenced by (in comparison) little fluctuations of ambient temperature...

@bluelight: The light output does not, but the required starting voltage does depend and a lot. And if the temperature drop so, the starting voltage is higher then the ballast deliver (the mains voltage in 230V areas), it does not ignite.