Ok, so long story short, I don't know what the problem was while my clients couldn't connect to the Internet, but it was gone the next day. I am using static IP addresses now, because the OSes of my clients are heterogenous (Windows, macOS and Linux) and only on Windows I got the hostname resolution running reliably.