Your query gets routed to different backend services based on “intent”, and I’ve noticed that sometimes I have to append “on Spotify” to get my request routed to what I imagine to be the Spotify-interfacing backend rather than the Amazon music one.
If you get routed to the Amazon music one, it just checks if the song is eligible for free tier play but doesn’t check Spotify at all. That’s my theory at least, and it kind of maps with the state of Alexa when I left it a couple of years ago. The service that routes based on intent should probably call both music services when the user has not specified a preference and pick the most useful response to send to the customer, and probably does, but for whatever reason I notice this behavior sometimes from Alexa.
Tl;dr say “on Spotify” to fix the issue. literally 5 years after I joined Alexa the same bugs and bad ux still happens and is apparently not being prioritized to be fixed despite Alexa being basically useless for anything besides timers, weather, music, and maybe the occasional fact lookup..