How do you locate something specific within an infinite, procedurally generated space?

As an example of what I am talking about, No Man's Sky will give players quests where the objective involves navigating to a specific location within the currently generated solar system.

Obviously the game is not storing the tens (or hundreds) of thousands of structures strewn across a solar system in data, it's locating them and then setting a waypoint, but how?

In my own project I have a 2D overworld. I also have quests, that I would like to point players to specific structure types (house, hotel, store, ruin, etc) when the quest is generated.

Currently I do this by running the terrain generator for X by Y tiles and have it check to see if one of those tiles is the requested structure. This mostly works... for now. The more unique structures I add the less likely this returns the location of a requested structure type.

One way to combat this would be to have a failed check try again by moving X tiles away from the last check in one direction, repeating until it finds what its looking for. This would work, but it could lead to very long loops unless I cap it, and then you just end up with failed checks again.

Any suggestions from anyone with experience in this?

Generally speaking, points of interest are usually inserted into a procedurally generated world where suitable at the time of generation.

Of course, it is quite flexible and as with any procedural system, you interpret the data to fit the form of whatever you want to do with it.

It's not (obviously) infeasible to create and store a list of hundreds of thousands of data points. Data is cheap. It would be even easier by a magnitude to only store points of interest which you can use to generate your quests from.

You can create this list at the same time your world is generated, or since procedural generation usually uses a seed, you can actually regenerate the exact same world from any given position when you need it, except the following time would be limited in scope to only whatever your quest requires.