It depends on your approach to random generation. What usually comes to mind with this term are the dungeons of Rogue, ADOM, Diablo etc., where the dungeons consist of a multitude of deliberately bland elements so that it really doesn't matter how the rooms are shuffled up. These games draw their fascination on mechanics alone; they are all about crafting new strategies from the multitude of skills and items available. As a large part of this community is more drawn to games like the classic JRPGs, which take much of their attraction from their dramatic, linear stories that require events happening in a certain order (basically the opposite approach), you probably won't find a lot of friends for such dungeons here.
However, I would opinion that even in story-heavy games there are enough locations where not every step must follow an order to serve the story. Does it really matter if the final encounter is in the upper left or the upper right of the dungeon? I think there is space for partial randomization which takes into account the placement of certain essential rooms, only shuffling up the passages in between or those where placement is irrelevant. Beyond replayability, this will also have each of your players face slightly different challenges. Personally, I'd find it appealing to know that I'm probably the only who has to face this exact dungeon.
Such limited shuffling would also allow for puzzles. Just make sure that the three rooms with the required hints/items are being placed somewhere before the room where the action has to be taken, and all is well.