The reason I assumed a non-branching path is because that's what most maze maps are like, they are not really mazes but obstacle courses. Making this assumption also simplifies the problem somewhat. I'm not really sure how I'd approach an actual problem of assembling a real maze... it seems like a kind of problem that should have a lot of literature already written about it, though, so maybe you could find and study that. If you don't feel like going all academic on the problem then I suggest you simplify it.
One possible simplification is working with a larger grid and/or smaller elements. In your example graphic, most of the elements are way bigger than I imagined them, the solution I described wouldn't work with them at all since the odds of getting any of the larger elements to in any way match the path would be practically zero. Like I said, I was thinking about elements up to 3x3 in size. (obviously, the biggest simplification you could make would be to make all elements 1 grid space big; however, I don't think we need to make the problem that simple in order to solve it)
It's also always possible to substitute clever algorithms with brute force; just randomly assemble stuff until you get something that meets some criteria; the problem here is that, if your success rate is low enough, you run the risk of randomly getting an absurd load time as the dumb algorithm may end up having to crunch through thousands of mazes to get one that works. Even then, there's not much guarantee that it works well.
That's another thing to consider: is the end result actually what you want from the gameplay perspective? Wouldn't it be frustrating for the players to dodge a difficult wisp wheel only to discover the path they were following was a dead end? I can understand the appeal of making it an actual maze, though, because it benefits the most from having randomly assembled levels. Still, even with that synergy, would a maze actually be more fun to play than an obstacle course?