As of January 2018, Microsoft has discontinued the Groove Music Service and moved accounts over to Spotify, but now my music search doesn't work. Is there a way to get this service back on my phone so that I can have it listen to a song and recognize the song?
Unfortunately, no. Cortana's ability to recognise music was retired along with the Groove Music Pass streaming service. Source: Neowin
You might try searching the Store for an app that offers similar functionality. SoundHound is one such app.
