I'd be inclined to be stingy with the spell, as it can already short-circuit adventures pretty easily, and not always to the players' advantage (in a redcnet storyline of mine, a player's clever use of the spell amost led to them bypassing every single clue that would have enabled them to thwart a plot against the queen. I threw more clues in their path so that they wouldn't have an uber-frustrating game session, but the clues I came up with were much more half-assed than what I'd originally planned).
That said, I'd agree that a location referenced by an object or creature isn't referenced at all. Players who looked for "the nearest exit that we've not already been through" couldn't do it, but if they were looking for "the nearest exit that doesn't look like any of the exits I'm currently thinking about" could do it: they're now defining the locations they're excluding by characteristics of the locations themselves.
WHre this gets really complicated is in the fact that locations are pretty much made of big objects, in some ways, and I wouldn't allow folks to search for those specific objects. No searching for the nearest vein of mithril, nor the nearest floor that's got dragon-claw scratches in it. However, I would allow searching for the nearest freshwater stream.
No searching for Joe's House, either, unless that's the name of the house. You could search for the nearest house, or you could search for the Three Falls Manor, but not for the house that Joe owns.
You're right that there's a fuzzy line. May I suggest a house rule? The less like a "pure" location the character is searching for, the less the spell succeeds. If you look ofr the nearest exit, the nearest house, the nearest river, the nearest forest, it works great. If you look for the nearest exit that you've not already seen, it may not give you all the warning about traps etc. that the spell normally gives. If you look for Joe's House, it may just give you a vague pull in the right direction. If you look for Joe's current location, Bigby's hand appears and smacks you upside the head.
Daniel