i had a case a couple of years back with my 35i that was similar. I say similar but it was always when the car had been standing for a while, but it did not happen all the time. I thought it was some sort of temperature sensor that determined how much fuel to inject when cold as opposed to when it was cold (like whatever it is that causes the engine to run at fast idle on a winters morning). however, a few times it ran bad for a few seconds (30s max) and then it cleared and run as sweet as a nut. car had only covered about 22K miles.
as it was in warranty at the time i took it in to the dealers and they were not good at diagnosis as the computer said NO!
this happened for a while and they suspected coil pack break downs, but again wouldn't change anything because there was no definitive fault that they could see. They had the car for a couple of weeks and still couldn't find anything or get it to repeat itself.
so i took to filming the start every time i started the car hot of cold! and eventually got video evidence it this problematic startup.
Mine would start lumpy with the rev counter bouncing about at around 3-400 rpm and running rough and lump. widening the tail pipes i did witness in conjunction with the lumpy running black smoke!
having been a trained and timeserver mechanic of the OLD ERA B.C. (before computers) i was able to make a series of assumptions. Basically black smoke is either caused by either insufficient air in the combustion process of excess fuel.
doing some further research in the inter web, i found some reports of this that was traced to leaking injectors when at standstill. in other words when running at normal engine speeds the injectors were doing the job they were designed to do. BUT at standstill with a reserve of high pressure fuel held in the pipe network right up to the nozzle tip of each injector some of them were letting past the smallest volume of fuel in to the combustion chamber.
The erratic nature of why the engine did not start poorly each time in my opinion (and i think it makes sense) is that the problem depended on when the crank/cam shaft stopped in the 4 cycles. in other words, if No1 injector had a leak, and the cylinder stopped with a valve open in that cylinder, i believed that over a period of time the cylinder could dry off the fuel that had been leaked in to it and not cause the problem on the next start. However if the No1 cylinder valves were both closed on the next engine stop, then no way could the cylinder allow for free air movement and the drying of the fuel in the cylinder.
The upshot!
i commented on this the dealer and they undertook to remove the plugs and injectors after running the engine for a period (road test) when the removed all six injectors 3 were found to have wet nozzles. QED!
they replaced all 6 injectors and the problem has never returned.
this will never show up in a systems check, as its a mechanical problem.
I've no idea how had it is to remove injectors on your engine, however if the fault happens in the way I've described, it could very well be the problem.
Do give me feed back as I'm interested.
Dario