[selectodude]

The more efficient the combustion, the hotter it is, and the more NOx is formed. Nothing to do with incomplete combustion. Nitrogen doesn't combust.

[Cogito]

Makes sense - it's not incomplete combustion but rather atmospheric contamination that allows for NOx products, and the amount of those is dependent on heat of combustion. Thanks!

[selectodude]

There's a not insignificant amount of nitrogen in the fuel itself, as well.