Questing for an item to me is all about implimentation. You don't need a compass or a random generator if you impliment the object correctly. Example: Joe Blacksmith needs a Gear for his smithy, You have explored the area or when you do you discover an abandon mine. aha the perfect place in which to find a gear because they were used quite often in mines. The Blacksmith could even suggest you search there.
Quest objects should be unique objects with a specific purpose in the game world and the item itself should provide a good hint in what it is to where it might be found. Also getting the quest could trigger additional conversation dialogues from town folk. When you are looking for a place what do you do? generally ask someone, so follow that structure in game as well. "it's south just on the otherside of the bottlebay bridge" "Thanks and Well Met!!"
The "mine" is a location. If the "mine" look like every other dungeon in the game there might be a problem similar to the problem I find in FNV where every "
Office Complex" or "
Apartment Complex" look very similar to one another, using the same kind of crates, boxes, shelves and lockers. You could simply name the location "The Mine" ofcourse but I think it's important that a location needs to stand out. Once you entered your tenth run-of-the-mill "Mine" or "Apartment Complex" and found nothing of value you cease to carefully look for unique stuff. Your mind have taught you routine/procedure and you may do so sloppy or faster than you would if the location had a sense of being unique or different.
FNV share a problem similar to that of Oblivion, even though it's better. It's a large world, but what you see inside buildings is usually the same. In this large world, handholding might be necessary because you cannot be expected to find what you need in a place as humongous as Fallout NV without good leads.
Of course, we can have some "Go There, Search the Lockers" in dialogue. I prefer such hints a lot more than a waypoint that lead all the way to the final
thingie. I would prefer though, that the quest is more than finding a needle in a haystack, so that both the thing you need to find, and the location in which you are to find it, makes sense. If you search for "the papers of the Overseer" you should expect to first find the room of the Overseer, then search that room.
Worst treasure in Fallout NV to me was the skill books. They are usually very well hidden in places filled with generic content and in places you do not really expect to find them. But I know, those aren't quest items and it might be unbalancing to find them all.
And by the way, I believe I lost track about what we were talking about since I actually agree with what you said.
