One (poor) solution I did was to add in the description a list of the videos in the playlists, so once a video was removed, I could just add it back.

I did that with only one YouTube playlist, so it wasn't too much work.