Hi Baratheon,
all puzzles including the random ones should have only one solution, even when you get down to the last couple of moves. If you find a similar situation please take a note of the level number. In the random curated levels there are seed numbers printed on the bottom right which would serve the same purpose. I hate process-of-elimination puzzles with more than one solution and would not want such levels in the game.
The undo problem appears to be related to the asterisks, I believe they're not being seen as moves in their own right but as extra hints to help make future moves. I'll fix that in a future update, I can see why it would be annoying to lose multiple asterisks (and crosses too maybe?) with one undo.