The problem with "complex dungeons" is that as soon as someone figures it out it becomes linear, with the sastasha example if you took it further and added to it, you will still end up turning into something like:

Go to A Find out what you need to press at B
Go to B press what you need to press
Go to Boss
Kill Boss
Get loot

Or

Go to A find part of the puzzle
Go to B find another part of the puzzle
Go to C find the mob that drops final part of the puzzle
Kill Mob
Complete puzzle
Go to Boss
Kill Boss
Get loot

Add any more complexity and you are asking for complaints or people will just pull everything in the dungeon to ensure the "key drops" or will just brute force the negative aspect of getting the puzzle wrong.

Multiple paths? Soon as you've done it once and figured out the correct path you will ignore the paths that aren't the right one. People already avoid trash when they can same kind of principle "this path is the best path to take"

I suppose you could make the boss spawn in three locations and randomise that and have each area add different mechanics but you still end up with a fairly linear dungeon just with a bit of annoying backtracking if you chose wrong first time. If they added a hint like to its location that run, then you'll just go there first and ignore the backtrack entirely.

Adding things like blocked paths or bonuses from one 8 man's contribution in 24 man content will just yield more abuse than there already is about how Alliance "A/B/C" sucks and needs to "L2P" They could have a boss that has 3 "bodies" that shares HP like the last Trash in WoD only with more mechanics however.

Going back to dungeons people will also make guides that have all the answers and people will expect you to know all the answers or to have the guide to hand so people will complain if you mess something up for "their run" they already do and we don't have complex dungeons to worry about.

Adding things like these to Raid content is probably the better idea because you aren't dealing with random people and raid groups actually communicate and know each other which makes a big difference to attitude.