914 Won't Start Properly When Cold

I am assuming you know that rotax choke system is different. The throttle must be closed or it will not function as intended. After engine starts you can disengage choke and apply throttle to warm up rpm. 

During none cold start, the engine will stop if choke is applied. You start second time without choke indicating you did not need choke that day but used choke just to confirm none was needed. Either case throttle if adjusted properly should always be at closed position if choke is applied.

I don't know if rotax like lycoming or continental aircraft engines has a cold temperature recommended preheat procedure. Lycoming recommends preheating engine if ambient temperature is 10 degrees F or below and continental 20 degrees F and below. 

You did not mention what ambient temp was. Have you tried preheating engine before start if it's really cold and see how things perform. Sometimes moisture gets between some spark plug gaps and freezes. 

I don't fly my gyrocopter with 912 below 50 F since its open and I have no heat. I have another aircraft with lycoming engine and I do preheat before start if it's below 40 F. 

Which 2 cylinders are cold???
Front vs Rear = Electrical Issue.
Left vs Right = Fuel Issue.

None are cold - it sounds like its only running on 2 cylinders but that isn't the case as all are hot as measured with infra-red thermometer

 Yes we have the throttle fully closed when using the choke. It doesn’t need to be that cold for the problem to happen – around 40 Fahrenheit/ 5 Celsius.

Warming the engine does help (we initially thought it was the ignition modules as warming them seemed to solve the issue, but I think it was just the general warming of the engine bay that did it).

The previous engine we had, did not have this problem so it’s very strange !

Thanks, Mark

Sorry!  I misread your 2 cylinder comment.
Assuming it is only on the first start of the day,  How long since the previous flight?
Are the electric fuel pumps running for any significant time before the first start attempt?