「単独の動画情報の取得」のAPIを使えば確認ができそうです。
http://gdata.youtube.com/feeds/api/videos/videoid
videoidの部分を適宜変更してください。
http://www.youtube.com/watch?v=vzx_hhQrVNA
の動画だったら、
http://gdata.youtube.com/feeds/api/videos/vzx_hhQrVNA
というリクエストを飛ばし、xmlが返ってくるかチェック。
削除されている場合は「Video not found」となるようです。
デベロッパー ガイド: Data API プロトコル - YouTube ? Google Developers
このソフトでできそうです。ただし、Windows専用ソフトです。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1032168775