From my experience, Winamp is pretty good at looking up and applying tags on music. For example, I've ripped about 100 music CDs through Exact Audio Copy as wave files in burst mode (relying on the AccurateRip for integrity) to reduce the ripping time and did a overnight batch process of converting them to MP3. I ended up with MP3s all containing the correct file names, but no ID3 tags. So I added the lot into Winamp's play list and ran its auto-tag (Select-all, Right-click on selection->Send to->Auto-Tag):. It took quite a while, but once it was complete, the majority of them had the correct title and artist information.
The only drawback with auto-tagging from online (regardless of the tool) is that the album information is not always correct, since a lot of songs are part of compilations (e.g. greatest hits, driving songs, etc. discs), so there's no accurate way of automatically applying the correct album info tags without doing this yourself or with a tool to apply the same album tag to multiple songs (e.g. based on the folder name the tracks are in).
As far as I'm aware of, all MP3 tagging tools, whether manual or based on online lookup, only change the tags and not the actual song data, i.e. the songs are never re-encoded.