This effect is not limited to p values obtained by simulation. P values are a statistic, i.e., a function of the data you have observed (and your distributional assumptions and model). As such, they have an expectation and a variance. The variance is due to sampling variability.
Suppose you run an experiment, observe data and calculate a p value using some parametric approach. Now suppose you re-run the experiment in the exact same way, so the data generating process of both experiments is precisely identical. You will still get different p values, simply because of the variation in your experimental observations.
P values are a statistic. They have a variance.
Suggested reading: Boos & Stefanski, "P-Value Precision and Reproducibility" (2011, The American Statistician). Also helpful: The dance of the p values.
I am aware that the exactness of my p-value will be at most an estimate because I am using the scores of my sample and not my population
This is a misconception. If you measure your entire population, then you don't calculate p values any more, because then you know the true population parameter - there is no randomness involved any more. As above: the p value's variability comes from the sampling variability.
If you are running a simulation, then you are actually in luck, because then you can re-run your simulation a couple of times and see how the p values change. This can be very enlightening.
Incidentally, the variability of the p value is one of the reasons I am slightly exasperated by people treating any p value < .05 as the Holy Grail and any p value >= .05 as career threatening. (Which it may well be in some fields.)
There is no rule we could give you to say which $n$ is enough. It depends on your data variability, on your model, on your misspecification etc.