I was able to achieve a similar result on my daughter's 06 Corolla by mixing a small amount of baking soda into some Dawn dishwashing liquid. Formed it into a paste that looked very much like Crest (LOL), rubbed it onto the headlight with a dry paper towel, and with only a modest amount of time and effort removed probably 80% of the haze. I suspect a second treatment would get it just about perfect.
I think the idea is to get any gently abrasive substance, eg baking soda, into a gentle viscous "carrier" substance, eg dishwashing liquid, is the key. Standard caveats apply on the type of "carrier" and "abrasive" you might use with regards to possible effects when inadvertently applied to surrounding painted areas :)