Do a regular search and use youtube.com as the search term, seeing as the search function looks at post content and titles it will find all the posts that have a youtube URL in them.
Search defaults to order by date, so the first result will be the newest post with an embed.
If your youtube videos are always inserted using the URL you could be a little more specific and use youtube.com/watch?v= as the search term.
Example code for use in a template file (barebones example).
<?php
// Args
$args = array(
's' => 'youtube.com/watch?v=',
'posts_per_page' => 1
);
// Setup query
query_posts( $args );
// Check query has results
if( have_posts() ) :
// Do the loopy loop
while( have_posts() ) :
the_post();
the_title();
endwhile;
endif;
?>