Video Embed Field: Check All My Videos on existance?
the quickest solution is to query the DB and export all youtube video IDs. 
After you can write a custom PHP script to check if the video exists.
Here is an example of the code you could use: https://stackoverflow.com/a/21069917

A more Drupalistic approach is to write a custom module which do the same thing. For example it could implement a drupal cron task or a batch procedure to verify each Youtube field content using the code suggested before.

I hope this suggestion will be helpful.