The structure is not incorrect. But this particular example is confusing, and therefore most people would prefer not to use it.
A typical example of the way the genitive marker -'(s) can be used with phrases in English is "the queen of England's", as in "the queen of England's promises", which means "the promises of the queen of England" and not "the queen of the promises of England". The way to think of this is not that the -'(s) is "targeting a previous, but not necessarily the last word in a sentence", but rather than the -'(s) is attaching to a directly preceding multi-word noun phrase: "the queen of England's promises" has the structure "[the queen of England]'s promises".
However, this works partly because people are used to thinking of the noun phrase "the queen of England" as a unit.
The phrase "the singer of that band" is not so familar, so people will be trying to process it "on the fly". This makes your first sentence, "He stole the singer of that band's wife," a "garden path" sentence—the reader initially sees "He stole the singer..." and thinks that the sentence will be about stealing some kind of singer, and then to get the intended structure "He stole [the singer of that band]'s wife," the reader has to re-evaluate the sentence after getting to the last word. As you and others have said, the effect is to cause some people to think confusedly "What does 'that band's wife' mean?"
"The wife of the singer of that band" or "The wife of that band's singer" is not prone to causing the same confusion; even "that band's singer's wife" would be less confusing than "the singer of that band's wife".