I've received a confirmation from a Replay Music developer, that he had tested MusicBrainz. He claims that Gracenote DB is much better.

Bottom line:

1. Use software supporting FreeDB or Musicbrainz for you CDs like Tag and Rename, MusicBrainz Tagger.
2. Use Replay Music to record music from online radio stations or online music subscription services (automatical tagging of individual songs is supported)
3. Use free Musicbrainz software to tag other individual songs. Although PicardTagger is CD oriented now, so I have no software suggestions so far.