Try explore map with debug mode - reveal overmap to see if it is a case (perhaps with new world if you don’t like spoilers)
I tried this, and miraculously, it revealed two labs in close proximity to me. I’m not sure how this is possible, given that the area that I actually explored is much, MUCH larger than the area I revealed with debug, but I guess I’ll chalk it up to really bad luck. Also, I’ll be sure to try that refugee center quest next time I have trouble finding a lab.
Thanks for the help everyone.