I don't think that other client software using Gracenote will be any better than Replay Music.

It would really be interesting to know whether there are any alternatives to Gracenote database and client software supporting them.

Many programs support CDDB databases. And CDDB is seems to be owned by Gracenote now. However software like Tag and Rename can tag full album
only (using CDDB disc identification), while Replay Music can tag individual songs.

gracenote.com has a list of partner software but it is next to impossible to understand from their lists what software can tag individual songs.