Quick update: I've been working on the headlights Friday afternoon and, after the first attempt botched them up real bad, all day today. On Friday, I used Mothers Mag and Aluminum Polish on the right headlight, which got around 85% of the fog out within 5-10 minutes. It was good enough that I decided to keep it that way. The left headlight was in much worse condition, and I decided to use sandpaper instead. It took me about 45-60 minutes of wet sanding, going from 600 -> 1,200 -> 2,000 -> 3,000 grit, and some plastic polish afterwards, and the results were amazing. Unfortunately, things went horribly wrong after I applied the clear coat recommended by ChrisFix (Rust-Oleum 249117). In addition to leaving a horrible orange peel much worse than can be seen in his video it started cracking about an hour after applying the third layer. Thus, after letting it sit for almost 40 hours I had to get out the sandpaper again today and redo both headlights from scratch. This time, I had to go much lower in order to remove the fresh layer of clear coat, and more granular to avoid scratches: 400 -> 500 -> 600 -> 800 -> 1,200 -> 2,000 -> 2,500 -> 3,000 grit. After applying much less clear coat I let it sit for 15 minutes, then started buffing out the orange peel with plastic polish. And it worked like a charm.
Unfortunately, I forgot to take a before shot of the right headlight. I hope there is still enough clear coat left for at least some UV protection. If not I will have to get a better clear coat because the stuff that ChrisFix suggested is horrible, and the orange peel is unacceptable.