I have also trying to get a custom post type year archive work for me (with paging).
My solution is as following.
First I created a custom template page (page_id=129) where I queried only the custom type posts, like:
$my_query = new WP_Query('year='.$myyear.'&post_type=project&paged='.$paged);
Next I added 2 rewrite rules. Here’s the code (inside functions.php):
// Rewrite rules for Project Year Archive pages
add_filter('rewrite_rules_array','wp_insertMyRewriteRules');
add_filter('query_vars','wp_insertMyRewriteQueryVars');
// Adding a new rule
function wp_insertMyRewriteRules($rules)
{
$newrules = array();
$newrules['projects/([^/]+)$'] = 'index.php?page_id=129&myyear=$matches[1]';
$newrules['projects/([^/]+)/page/?([0-9]{1,})/?$'] = 'index.php?page_id=129&myyear=$matches[1]&paged=$matches[2]';
return $newrules + $rules;
}
// Adding the id var so that WP recognizes it
function wp_insertMyRewriteQueryVars($vars)
{
array_push($vars, 'myyear');
return $vars;
}
So now I can call for example https://mydomain/projects/2010/ or https://mydomain/projects/2010/page/2/ to get projects from a specific year (and page).