Sebastian, does this happen with all (or most of) your albums or only with a specific one?
I've tried it here and the try again option only comes up, if the server didn't return a valid result. I'm currently using at.freedb.org, because freedb.freedb.org has major problems the last weeks.
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".