The game states that decks get reshuffled when empty, but I'm wondering if that was really the intent with the questing system. In our first game we went through all 25 quests and that was with everyone only have 1 hero for most of the game (one guy had 2 for a while). Granted, some cards and events let you trade in quests so you go through more of those than rewards. I don't think we quite got through all 25 rewards, but it was close.
Given you get a reward on a completed quest, I'm wondering if it makes more sense to simply be out of quests after the 25 are completed. An uncompleted quest stick around, like ones you discard rather than complete. Similarly, reward cards never get reshuffled either. If you turn 3 of them into a rune token those 3 are gone from the earth.