Could the GPG keyserver chosen from the pool have been temporarily down? I see that sort of thing quite a bit. THe command above worked for me on a regular VM.
And/or it could be an outbound firewall issue? I think the default remote port for keyservers is TCP 11371?
You could force a keyserver, as well as forcing HTTP port 80 on the end, e.g:
gpg --keyserver hkp://ipv4.pool.sks-keyservers.net:80 --recv-keys 916B8D99C38EAF5E8ADC7A2A8D66066A2EEACCDA