It's not that there is unburnt fuel in your exhaust - unburnt fuel, while a pollutant, is not the problem.
The issue is that higher temperature combustion, while more efficient, produces much more NOx. So you get more energy per unit fuel at higher temperatures, but you also get more pollutants. Lower temperatures (less oxygen) result in "cleaner" combustion (essentially, more CO2 and N2, less NO and NO2), but produce much less energy per unit fuel.