My own experience suggests that if you pick who you ask reasonably carefully (e.g. followers of that god, and not of a religion that would not be inclined to help you), you will probably at least get a hint of where to look. For example, there was one god I followed whose shrine was "amongst a humble people" or something like that. Someone told me that these people lived near to a particular city, at which point I found the shrine in the surrounding areas of the ruined city.

The only reason I can say this now is that that shrine is gone from the game.