Happens with some ABBA albums, some Toto albums, all my Pink Floyd albums and some of my Rolling Stones albums (some because I did not test all).
MP3Tag shows me a list with possible matches and when I choose one, I get the error posted above. I tried with all mirrors.
The freedb-ID is based on the selection. So, if I do a web-search for "The Definitive Collection" (album only) and select the 3rd item, I get "2811dd13" as ID, if I select the 9th item, I get "e811a011".
About the other questions: no, I don't have the CD inserted, and no, I am not using determine from selected files, but determine via web-search.
If I open EAC and tell it to obtain the information from the remote freedb database, everything works, so I doubt it's a problem with the server. Also, the firewall isn't blocking MP3Tag.
Edit: If I use determine from selected files, I get "The server failed to return a valid query response code".