Having "The Trial" be quest #3 could help retain that old (1st edition) Lore of "becoming a Champion" and gaining the 500 gold (each) as a reward.
I will admit when I play I still don't shuffle the Treasure cards before EVERY search. I do one thorough shuffle before the quest begins and then that's it until it's over. But that's how I do it. I also use a deck that has 10-15 extra cards added to the standard NA Treasure deck (mostly good, but a couple of bad, the odds of getting a good card without shuffling are only slightly better than the base deck).
When I stream games on Twitch I also implement a house rule called "Bonus Treasure Search" that people in chat can "buy" using channel points (gold coins that acquire over time, with more given to subscribers!). These are "expensive" but I allow a Hero to search a room one more time than they normally could and the search will be a "safe" one (if Wandering Monster or Hazard card is drawn, ignore it and draw again until a "good" card is found... similar to "Treasure Without Doom").