Smaller units (say 100KVA or less) shouldn't have any problems, as long as they are kept warm enough.
If you get much larger than that, natural gas units become very expensive compared to diesel. So I'm not sure what their starting times would be. I've never seen a natural gas generator larger than about 150KVA.