I work with Spotify links and the Spotify API regularly for work and have never seen a link to a playlist or track randomly 404 or not work. Spotify share links are really basic, they're just an ID and type of link, like "/track/{id}" or "/playlist/{id}".

Not saying you're wrong, I've just personally never had issues with them, and I work with lots of share links from a variety of artists.