problem with flame control in a natural gas grill
Firstly, tune your burner for a good flame when hot, rather than a good flame on start. Without knowing anything specific to your burner, I can only speculate on the more generic aspects.

Two most probable causes: reducing flame and sodium flare.

The most likely which is also what you suspected - flame stoichiometry, your air to fuel ratio. There are several possible causes. It could be a not so carefully designed air intake path or valve(s)/adjustment mechanism not holding settings any more because of age or corrosion or fouling from grease/soot/char/salt. You might want to to some cleaning, look for blocked nozzles and grease/char on the moving parts of the burner adjustments. Grease in moving parts can be a nuisance as they soften upon heating. Another common problem is that prolonged small flame settings could sometimes burn out the jets (design dependent) and upset flow rates (more an issue for surface mix type rather than pre-mix type burners).

What you have is a reducing flame, insufficient oxygen flow to match the flow rate of the methane so that it burns incompletely in the time available. It is not so unusual for a blue neutral flame to end up as either as an oxidising flame (blue but with too much oxygen) or a yellow-orange reducing flame in a poorly designed burner as it heats up, either the air path is heated up or the gas path is heated up or both.

Combustion, like all reactions, is about mass not volume, and more precisely about molar mass. As gases heat up and expand, the same volume contains less mass, fewer molecules. If your air intake path is heated up, the same volumetric flow has fewer molecules in it. So what was a well adjusted air flow for your natural gas flow gradually became insufficient and you end up with a reducing flame. You will need to readjust your air-fuel ratio again when it is hot. More likely is that both your methane and air paths are heated equally, but the two expand differently, and more importantly, the volumetric molar masses vary with temperature unequally for them.

I can go into a numerical explanation if you wish (let me know and I can add that in an edit later).

There is nothing you can do about your burner design. You can still make it work by increasing your air flow to achieve a neutral flame once everything is hot (you have to choose at what temperature you wish to have a neutral flame). If there is no way of adjusting that at temperature, you will just have to do it when cold by trial and error.

What you will likely end up with is an oxidising flame (long blue central cone, hissing flame) on starting. Depending on your burner, you may end up with a difficult start with an unstable flame, even blowing itself out when cold or an acceptable one. Once heated to your chosen temperature, you will have a neutral flame (blue, shorter central cone, perhaps even with a yellow tip in that cone). And at temperatures higher than that a reducing flame that is yellow again. 



I would still give it a good clean. It is possible that you have an accumulation of salt on the burner emitting sodium flare when heated. When cold, nothing happens, but when heated, salt does not really burn but emits a yellow glow like some street lamps despite having a perfectly balanced neutral flame. This is also very probable actually.



Numerical part (requested by @joshua_engel)

Assumptions:

30,000 BTU/h burner output, 80% efficient

Air is just 21% oxygen and 79% nitrogen by volume, natural gas 100% methane with complete combustion heat of 891kJ/mol

Perfect stoichiometric combustion for neutral flame

In moles: 1CH4 + {2O2 + 7.5N2 } → 1CO2 + 2H2O + 7.5N2

In kg per hr to produce 30,000 BTU:

0.71CH4 + {2.84O2 + 9.36N2 } → 1.95CO2 + 1.60H2O + 9.36N2

12.2 kg air and 0.7 kg natural gas every hour

At an ambient temperature of say 20C and around 50% relative humidity (ignored in air ratio calculations), you need about 10m3 of air and a touch over 1m3 of natural gas every hour.

Natural gas is piped in at pressure (will cool when expanded at burner) and air is just pulled in from the immediate surroundings. Thus, gas temperature is much less affected by the burner's heat than air is. Burner air settings dictate volumetric flow and not mass flow. If air at the inlet to the burner was heated from 20C to 70C which is a likely underestimate (relative humidity would have dropped to around 3%), then the same 10m3 of air would only have 10 kg of mass. Within that, there would be only 2.4 kg of oxygen instead of 2.8 kg. You no longer have a complete combustion and there would be carbon monoxide (burns blue) as well as soot (glows yellow or red). Your air adjustment has to go from 10m3 to almost 12m3 to compensate.

If it was propane, fuel temperature would likely be much lower than ambient because of vapourisation cooling and adiabatic cooling when released from the tank. That would mean much denser fuel and much more air needed.

Of course, you would always set your burner to run at say 5-10% or so excess air, but even then, a modest 50C rise in air temperature would drop air density by 15%, enough to push the flame from neutral to reducing. 

This is a fairly simplified illustration. In reality, humidity, flame temperature and gas densities are circular.