Thanks for your report.
This was more meant into the direction of excluding this as an additional, potentially problematic, factor. I didn't intent to suggest using a VPN (I don't do it myself).
Even when you say
there is still a (slight) possibility that all the addresses you got in between were problematic. Even when it is unlikely. A more likely explanation could be that the Internet routing of your ISP to the individual name servers of the problematic domains could have been broken so they couldn't be reached.
Anyway, when a reinstall solved it and you configured things the same way, it is almost impossible to find out what changed. It may have been a configuration oddity in your first setup, but, hostestly, I couldn't think of a way to trigger what you saw.
Good that is resolved now and let's hope it won't ever happen again.