My research agrees with your advice. The prices for those apps are reasonable, too. One thing I noticed, but didn’t look too closely at, is that those apps seem to be able to write the metadata only to ID3 tags. It is my vague understanding that FLAC doesn’t use ID3 tags (normally)?
The amount of work involved is starting to look daunting. I still have a Mediamonkey license, and it can organize your collection by bpm, if the tag is there, and I think Mediamonkey also has a pretty robust smart playlist generator. Hmmmmm… At the very least, one could shuffle through a focused playlist like that and tag the tracks one wants to incorporate in future bpm-based playlists. Maybe it’s doable.