Getting somehow from all lists, I would expect a DNS problem, also stating "... record not found" looks a bit like your DNS server is not able to resolve the names. Try nslookup on any domain, you're sure, it should resolve. Also check the name servers stated in the response, maybe they are unusable or down. My recommendation is to set up your own DNS server on PMG directly, if you have nothing in your internal zone already, e.g. unbound as stated above. For private I'm doing so, for commercial, we use our centralized own DNS server on the Firewall device, same for the time server.