It does sound fun, but there would have to be some layer to control the amount of wackiness, or it would feel random to the point of meaninglessness, like "procedural oatmeal"?
Fixed set of items in a fixed set of locations. Certain locations need certain items to access. So therefore randomize which items are in which rooms while still being able to complete the game.
Then they have a door randomizer which changes where doors warp you to - effectively changing the map and potentially the order of items needed.
So this part of the puzzle generation isn't that bad, you also need to make sure you can't make it unsolvable by destroying/wasting items or making them inaccessible (or allow this and call it "Sierra mode"). Making the item usage interesting is the hard part, but that's not as much as an issue for a Zelda game.