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) ...
In short, your code is fine, but the custom query's pagination and the one for the main query, they can't be using the same paged URL query string (which WordPress reads the value from for the paged query arg used in a WP_Query request).
Why the error 404?
So for examples, paginated/paged category requests can have one of these URLs:
Full pretty URL: