Without actually looking at it in person, that's a tough call. You might try the clay bar. I like the gas idea simply because it's way less aggressive, especially if you're prepared with the soap ant water and just do a small section at a time. If you're just dying to get the sandpaper out, I would start with something really fine, like perhaps 1500.
