I just tried out Clementine, and with lots of features disabled it looks clean and seems to work well. However, I don't see how to display songs in order of least recently played to most recently played. However, Clementine did show the songs that Rhythmbox was "missing," and I now suspect the issue was that Rhythmbox was categorizing them as Bryan Ferry songs, not Roxy Music. Clementine was smart enough to include them in the Roxy Music search.
Double-checking with Rhythmbox, they are indeed under Bryan Ferry and not missing. So this is not a new Rhythmbox bug.
Guayadeque is promising, but it forces a listening model on the user. Also, I can't get it to use the screen efficiently. If one doesn't keep a bunch of useless crap on-screen, instead there's a big blank area. If there is discussion of layout, saving layouts, restoring layouts, etc., why isn't the layout configurable? I might have another look in the future.
Please don't mention Banshee. It's got too many features I don't need, takes forever to load, takes forever to search a large library, and so far as I can tell does nothing well.
Upshot: I'll keep using Rhythmbox since I don't have time to mess with Guayadeque right now. I'll uninstall Clementine. I'll keep Guayadeque to mess with in the future.
2.96 might be an oldish version of Rhythmbox, but it's what's in the Mint 13 repositories, and there's no sense in wasting much time tweaking a media player--it works or it doesn't In the next OS upgrade (later this month for me), it'll either work or it won't.