Adapted from the Codex, tweaking WP_Query to get all years before this.
Untested, but should work.
$on_this_day = array(
// remove the year from the first query array
'monthnum' => date('n'),
'day' => date('j');
);
// Create a new filtering function that will add our where clause to the query
function filter_where( $where="" ) {
// posts for all years before this year
$where .= " AND post_date < " . date('Y');
return $where;
}
add_filter( 'posts_where', 'filter_where' );
$query = new WP_Query( $on_this_day );
remove_filter( 'posts_where', 'filter_where' );
if( $query->have_posts() ) : while ($query->have_posts()) : $query->the_post();
$year = get_the_time('Y');
$month = get_the_time('m');
$day = get_the_time('d');
echo '<a class="on-this-day" href="'.get_day_link($year, $month, $day).'" title="On This Day in '.$year.'">';
echo 'On this day in '.$year;
echo '</a>';
endwhile;
endif;
UPDATE
Updated code with the complete loop. It should now output a list of links for the years past, leaving out the years with no posts for that date;