Is there any reason for inns to stick around once the quest they offer is complete?  I find myself wasting time sending heroes to inns with no quest because I forgot I already did it (or maybe the AI did - does the AI do quests?).

In any case, some suggestions:

• make the inn disappear once its quest is done, like most of the quest target buildings do.
• Indicate the inn quest availability in the information box when you mouseover the inn on the map.  It can say something like "Quest available" or "No quest available".
• Give the inns some purpose besides dispensing a single quest, such as a way to quickly heal your units for money, a store to buy certain items from, randomly spawn recruitable NPCs, etc. 
• Have inns generate new (level-appropriate) quests and the game goes on.