Yes, it has happened to me on Spotify multiple times. More often, they change a song with a different version (e.g. same song from a different album or recorded live performance)