The issue "fixed" itself (as in I can now connect to sites, I haven't checked if it actually uses the correct DNS yet) once I returned from my vacation, so it is related to roaming.
My working theory: my device used my provider's DNS, which is located in a different country, and the timeout for getting answers from the DNS server might be low enough to cause issues.
Is there a way to modify the timeout settings?
Also I"m not sure I want to give this topic the fixed tag yet, since I still get the feeling that this problem shouldn't have happened if the correct DNS server was actually selected.