This is really interesting one! I\'ve tried to solve this, and here is what I ended up with.

With a pure SQL, we have an ability to get all distinct years of all our posts with the following SQL request (recipe founded here):

SELECT DISTINCT YEAR(wp_posts.post_date) FROM wp_posts

getting something like this:

mysql> SELECT DISTINCT YEAR(wp_posts.post_date) FROM wp_posts;
+--------------------------+
| YEAR(wp_posts.post_date) |
+--------------------------+
|                     2017 |
|                     2018 |
|                     2019 |
|                     2020 |
+--------------------------+
4 rows in set (0.00 sec)

But how to combine this with our main query, especially taking in account all the search criteria etc? Well, we have a posts_clauses hook where we can get all the request clauses. We need to save this clauses for later use, and we have to make sure we are dealing with the main query clauses. Here is the code (this one goes to the functions.php):

function check_query_clauses( $clauses, $query ) {
    if ( $query->is_main_query() ) {
        global $main_query_clauses;
        $main_query_clauses = $clauses;
    }
    return $clauses;
}
add_filter( \'posts_clauses\', \'check_query_clauses\', 10, 2 );

The $main_query_clauses array would consists of the following fields:

Array (
    [where] => ...
    [groupby] => ...
    [join] => ...
    [orderby] => ...
    [distinct] => ...
    [fields] => wp_posts.*
    [limits] => ...
)

Not all of them will be needed in the future. Next, going to your search.php template, here is the code which we\'ll use:

global $wpdb;
global $main_query_clauses;
$years_query =
    "SELECT DISTINCT YEAR({$wpdb->posts}.post_date) FROM {$wpdb->posts} {$main_query_clauses[\'join\']} WHERE 1=1 {$main_query_clauses[\'where\']}"
    . ( $main_query_clauses[\'groupby\'] ? " GROUP BY {$main_query_clauses[\'groupby\']}" : \'\' )
    . ( $main_query_clauses[\'orderby\'] ? " ORDER BY {$main_query_clauses[\'orderby\']}" : \'\' );
$years_results = $wpdb->get_results( $years_query, \'ARRAY_N\' );

Note that we don\'t use \'limits\' clause here (as well as \'fields\' or \'distinct\' ones). At this step we\'ve got something like

Array (
    [0] => Array (
        [0] => 2020
    )
    [1] => Array (
        [0] => 2019
    )
    [2] => Array (
        [0] => 2018
    )
    [3] => Array (
        [0] => 2017
    )
)

The last piece of code is

$years = wp_list_pluck( $years_results, 0 );

and we are finished up with

Array (
    [0] => 2020
    [1] => 2019
    [2] => 2018
    [3] => 2017
)

Depending on your search criteria the years in array may appear in different order, so you should additionally sort it according to your needs. Voila!

Update

After you select a particular year your query would change and this code would produce an array with only one item. To fix it you\'ll need to remove the year filter part from WHERE SQL clause:

global $wpdb;
global $main_query_clauses;
$pattern = \'/\\sAND\\s*\\(\\s*YEAR\\s*\\(\\s*\' . $wpdb->posts . \'\\.post_date\\s*\\)\\s*=\\s*\\d+\\s*\\)/is\';
$where = preg_replace($pattern, \' \', $main_query_clauses[\'where\']);
$years_query =
    "SELECT DISTINCT YEAR({$wpdb->posts}.post_date) FROM {$wpdb->posts} {$main_query_clauses[\'join\']} WHERE 1=1 $where"
    . ( $main_query_clauses[\'groupby\'] ? " GROUP BY {$main_query_clauses[\'groupby\']}" : \'\' )
    . ( $main_query_clauses[\'orderby\'] ? " ORDER BY {$main_query_clauses[\'orderby\']}" : \'\' );
$years_results = $wpdb->get_results( $years_query, \'ARRAY_N\' );