Once a goody hut has been completed it should phase from the map either on completion or phasing out after 2-3 turns thereafter.  One map I had was so covered with goodie huts/ruins that expanding a few cities became problematic.

Also, with so many icons on the screen it becomes impossible to recall which ones you'd already visited

Yeah, I've had that same exact issue BernieTime.  It also makes these quests feel wayyyy less epic.  Seriously, by just wandering around my starting city my heroes were getting so much gold, resources and magic items it basically turned them into gods!  It just doesn't feel very epic to me when the quest sends me to a location.... within sight of my capital

I'd say the level 1 quests, sure... they can be right near your capital.  Perhaps the level of the quest determines the range, so the higher quests minimum range to spawn is still a bit out from your zone of control.  Would feel like an adventure going into the fog of war to recover this ancient powerful doodad, who knows who or what you'll meet!  Much better than...  oh, this ancient and powerful doodad is... right on my trading route between my two oldest cities.  Wonder why we never noticed this massive collection of ruins before... 

There are far too many goodie huts and quests littered around. Decrease the quantity, increase the impact. Especially for higher level quests & goodie huts. Also quests should always produce something much more unique than what goodie huts give.

Goodie huts: generic weapons and other equipment, books, gildar, materials, potions, maps, small amounts of very rare materials (this is something that should definitely be gained from high level goodie huts) and occasionally, very rarely something quest-levelish

Quests: magical weapons and equipment, spell books, spells, large stashes of gildar & materials, new units