If anyone else in Poland connecting through Orange has this problem, please report it to Orange. I did, in fact twice.
The main issue is that >ping id.remoteutilities.com returns "Request timed out", although the IP address of this DNS server is found properly. With tracert it can be readily seen that the packets get stuck somewhere on the way.
BTW, the IP of id.remote.. is 126.96.36.199. The last server in tracert for this IP is 188.8.131.52, an Orange server. Both these addresses are listed as blacklisted by dnsbl.spfbl.net . Interesting.
Indeed there was an incorrect reverse DNS for that IP address (perhaps, inherited from previous IP address owners). Unfortunately, the hosting provider didn't clean that up. So thank you, Leszek, for bringing our attention to this issue.
Now we updated the reverse DNS record to id.remoteutilities.com and you can ask Orange to stop blocking our IP address.