Windows Central had the original story here:
In the past, tapping the music icon on Cortana's UI let the artificial intelligence service act like a glorified Shazam identifying any music playing. The link would then take users to the Microsoft Store to view the album or optionally buy it. Without the music store, however, there is no real next step for the user unless Microsoft wants to feed customers to Amazon, Apple, or Google, who all maintain music stores (for now).
With the elimination of Groove tapping the icon now results in an error with "Song unrecognized" and Microsoft slipping in a not-so-subtle "this service has been retired."
Jason Deakins, who works on Cortana and search at Microsoft confirmed the end of the service in a tweet responding to myself and @faltermayer:
Hi @faltermayer, that is correct: due to the shutdown of the Groove music service, Cortana's music recognition functionality has been retired.— Jason Deakins (@JasonDeakins) January 3, 2018
This is what anyone will see going forwards:
It's a minor feature in the grand scheme of things and I can't remember the last time I used it, but it's a definite chunk out of Cortana's intelligence and you'll now have to rely on friends with iPhones and Android handsets when playing the music recognition game in public.
PS. Shazam still works fine, it's here in the Store if you look via this link (it doesn't come up in Search because Shazam withdrew it officially some time ago). If that doesn't work for you and if you grabbed in the past, re-install it from My Library on the Store hamburger menu.
PPS. David Ross has pointed out that the old Windows Phone app SoundHound still works fine. Screenshots below: