custom permalink/shortlink with base62 encoded post ID

You only made a mistake in the final step, when you convert the base62-encoded ID back to a decimal ID. You should not do this by changing the rewrite rules, as they are only patterns, not actual rules per post.

What you want is take an incoming URL, let WordPress parse it using the rewrite rules, but then before it is passed to the query engine, check for the post_id62 variable and set the actual p (post id) variable based on it. You can do this in the request filter, which is applied in WP::parse_request().

add_action( 'request', 'wpse22253_request' );
function wpse22253_request( $query_vars )
{
    if ( array_key_exists( 'post_id62', $query_vars ) ) {
        $query_vars['p'] = base622dec( $query_vars['post_id62'] );
    }
    return $query_vars;
}

However, this will not solve the postname-N problem. WordPress will still call wp_unique_post_slug on the post_name field, and post_name will not include the post_id62 part (since the database is independent of the rewrite rules). As Mike suggested in the followup comments to his answer, you should either figure out a way to include the post_id62 part in the post_name field, or (and this might be the better way) ignore the %postname% part in the URL and just slap a postname-with-stripped-number-suffix string at the end.

You will also run into issues with your shortlinks, since they have the same format (any letter or digit) as a page. Is /banana/ a page with the title “Banana” or a shortlink to the post with ID 34440682410 – which is banana in your base-62 encoding?