Wenn die NATS Wegfahrsperre probleme macht dann blingt die Motorkontrollleuchte wenn der Schlüssen auf Zündung steht!
Das bedeutet dann das das Schloß den im Schlüssel befindlichen Code nicht auslesen kann.
Hört sich bei dir so an als würde dein Magnetschlater nicht mehr ganz funktionieren und das Anlasser Ritzel nicht weit genug in den Motor bekommen.
Kohlebürsten würde ich bei deiner Beschreibung ausschließen da der Anlasser ja dreht und die Kohlebürsten somit den Strom noch übertragen.
Evtl. könnte es bei dir auch die Benzinpumpe sein. Kabelbruch in der Zuleitung (würde das mit der kälte auch erklären) achte mal drauf wenn du den Schlüssel auf ACC stellst ob du ein leises Surren von Ihr hörst