Theoretically you could more or less do this as you progress through the game so some of the locations don't need to be out of your way. I was thinking these riddles would be hidden in existing dungeons and caves and not necessarily in places set up just for them (excluding the treasure hoard of course) or in towns. It wouldn't make sense for them to be hidden directly near roadways though, so that convenience is out.

Who's to say the riddles won't make you think? I'm not talking about you get to this point and it tells you precisely where to go next, that's too easy, not to mention boring. Of course without the precise location it might lead to more walking...
Personally, I never minded the walking, it was a bit slow at times and I would have appreciated it if dungeons had a quick way out, but once out of them I always quick traveled (If that option were available at the time).
Anyways it's just an idea and something I, at least, would like to see in book II or III.