YouTube now shows a warning at the top of the page when some of the videos from a playlist have been deleted from YouTube. The warning is only displayed when you open the playlist and there's also a button that lets you remove the videos that are no longer available.
Unfortunately, YouTube no longer shows the title of a video after it's been deleted. This was useful because you could find similar videos and add them to the playlist. Now that YouTube replaces the title with "deleted video" and the video page only shows an error message, YouTube could automatically remove the missing videos.
{ Thanks, Sterling. }