Sometimes it can take up to several (real) minutes.
True. Though the player can "trigger" particles if he shares the same space and "collides" with them. Then possibly all other particles in the same cell will start to work as well.
Anyway there's a solution to this. All you need to do is to add "dummy" NiControllerManager which actually does nothing. Particles with editor markers and with NiControllerManager always start properly as they should (there's no need for triggering them or waiting).
Here's http://www.4shared.com/account/file/FAWAYu6h/smoke-manager.html I created with medium smoke (meshes\fire\smokemedium.nif) and with added simple (and almost empty) NCM. It works properly in my game anytime unlike the "clean" particle meshes.