RESOLUTION
Plesk connects Parallels License Server (Key Administrator) at 5224 port for the license update procedure. Make sure that the outgoing connection to ka.parallels.com:5224 is not blocked on Plesk server or somewhere in the net. This can be examined with commands:
# nmap -P0 -p5224 ka.parallels.com
# telnet ka.parallels.com 5224
# traceroute ka.parallels.com Keywords: cannot update plesk key license failed