Your problem is not common, which is why no one is offering a sure fix. Most often, Gracenote simply has no info on the track(s) being looked up.
Have you used the forums' search feature to find out what others having this problem have tried. Among the suggestions I remember seeing are fixing corrupt files in the "Winamp/Microsoft.VC90.CRT" folder, removing an interfering 3rd party plug-in(s), and making sure WA is allowed thru the firewall. WA uses the IE browser engine, so having the WA browser access the Internet is no guarantee that WA itself has access.
However, you seem to have ruled out those 3 particular things, by disabling the firewall (not recommended) and doing a clean uninstall and reinstall with only official WA components.
Since it used to work for you, can you remember if anything else changed on your system (hardware and/or software added or removed) around the time it stopped working? A computer system is so complex that sometimes something that makes no sense being related to a problem turns out to be the problem.
Was it a different version of WA that worked? If so, clean uninstall and install that version and if it works, run a 'One for Nunz' report in order to look for differences between it and your current installation report. FileHippo.com is a good site for finding old WA versions.
Solving problems like this is like finding a needle in a haystack. Not a lot of fun, unless you have patience and accept the challenge of such things.
Win 7 Home Premium 64-bit SP1, WA Pro 18.104.22.16892 beta, cPro MPxi_remix skin, 5.1 speaker system