In the movie I just finished, I had to save a long (continuous) take where a popular singer (here in Italy) singed with playback but was out of sync (in a few spots more than half a second). Obviously the out-of sync is not constant, as the singer sometime was on the beat, sometime late, etc. This shot was edited without cuts, and the production guide track was obviously substituted with the studio recording (that was used for the playback during the shooting).
Recording the song again, with the tempo mapped to her singing, was out of the question (for budget and agreement problems).
I asked for the instrumental track and the voice track. Then I stretched, moved, edited every single line/ word trying to match the lip sync, but always paying attention to the musical rhythm. On two or three spots I had to slightly time stretch the music too. In the end, the resulting sequence is far from perfect, but much better then the original, and the production approved and signed the edits, everybody was happy. But...
But how would you have dealt this? Time stretched music and voice at the same time? (I tried, but to me the result was much worse and the flow of the song completely destroyed). Found the sync for the voice part, and then remap (with time-stretch) the instrumental track?