Zelda and Portal 2 did this very well. The problem is if you don't do it well, it becomes a nuissance and becomes a negative instead of a positive. Much of the examples given from FF11 were puzzles done VERY poorly.

Thousand Maws almost had it, by having the multiple paths and the different methods of unlocking them. But it has to be like something where... you walk into a big room, and you see that your path is blocked, and at first you don't see any way across.... but by exploring the room and discovering various mechanisms/magic devices, that do various things, that by combining them in certain ways and in a certain order, the path could be unlocked, or if you make a mistake, enemies flood the room.

That said, FFXIV IS NOT A SINGLE PLAYER GAME, and just having a single variation of the puzzle really is not acceptable. You have to have first multiple variations, and then you need to make it hard for players who have attempted and completed the puzzle multiple times to solve the puzzle just from memorization alone. Otherwise the puzzle becomes a chore.