You are left with an empty space in your playlist that gives you no clue as to what had been in that slot.
The work around is to use the Add / Edit notes feature of the playlist.
Click [Add / edit notes], and in the dialog that pops up, highlight and copy the name of the video, then paste that text into the text description.
Now click Save. Now, if the owner of the video deletes the video, even though the title of that removed slot in your playlist will still say "[Deleted Video]", now your custom text will still be there, telling you the name of the video that was removed. In most cases, you can find another copy of the same video and re-attach it to your playlist. Problem solved!
Enjoy!