See this thread for official info.
you can hit this: http://gdata.youtube.com/feeds/api/videos/VIDEO_ID (Page now returns: “No longer available”.)
and determine if the video is valid based on response
There’s no way you can check the validity of the ID with RegEx, since not all alpha-numeric values are valid ID’s.
p.s. i’m pretty sure i saw “dashes” in video ID’s
p.p.s. “underscore” is a valid character also: http://www.youtube.com/watch?v=nrGk0AuFd_9
[a-zA-Z0-9_-]{11} is the regex (source), but there’s no guarantee that the video will be there even if regex is valid