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.