TLDR: Genius issue still being investigated, send
feedback to Apple if the issue impacts you. Free tier of Google Play has Genius equivalent feature that works well.
Just an update to my post, I did reach out to the Apple rep that emailed me back in December for an update and they said the issue was still being 'investigated'.
One slightly bizarre thing I have noticed in the last month, I have come across 2 new tracks (released in 2016) that haven't worked before with genius on my iPhone (iOS 6 with iTunes Match) that now work, but when I save the genius playlist and look in iTunes, it does shows up, but any new songs in the playlist are not visible in iTunes. If I try to create a Genius playlist for one of those two tracks in iTunes, it doesn't work, even after another update of Genius. Strange.
An interim solution, I recently upload my entire library for free with Google Play. The free tier works exactly like iTunes Match and the instant mix feature seems to work exceptionally well. Instant Mix is exactly like Genius except, you can't expand more than 25 at a time. There are also stations for your music library like Genius Mixes. And there is an iOS app for it, completely free.
This might be an appropriate alternative for now for anyone looking for Genius alternatives.
For any new readers of this thread that want to see Genius fix, please send
feedback.