I had both my phone region and Xbox region set to USA (while living in the Czech Republic) - both Cortana and the Music Search worked. I then migrated my Xbox account to Czech Republic (naively thinking it would make Xbox Music work - well, it didn't :straight and the Music Search option disappeared. I waited for 3 months to be able to migrate my Xbox region back to US, but even after a few days the Music Search option hasn't come back.
What exactly determines whether you can use the feature or not? Phone region, Xbox region, something else?