Custom Permalink Tag breaks Pagination

Most the below work stems from a previous question / accepted answer. I’m trying to achieve the following permalink structure:

/listings/
/listings/page/2/
/listings/%state%/
/listings/%state%/page/2/
/listings/%state%/property/post-title/

I thought it was going to be a simple task but I keep running into more and more issues. Currently, all the above works except pagination.

My Post Type ( cpt_listings ) rewrite looks like this:

'rewrite' => array( 'slug' => 'listings/%tax_states%/property', 'with_front' => false )

My Taxonomy ( tax_states ) rewrite looks like this:

'rewrite' => array( 'slug' => 'listings', 'with_front' => false, 'hierarchical' => true )

I use this function to replace %state% with the actual taxonomy term:

/** Process the State Taxonomy Permalink Tag **/
function state_permalink( $permalink, $post_id, $leavename ) {

    if( false === strpos( $permalink, '%tax_states%' ) ) {
        return $permalink;
    }

    // Get post
    $post = get_post( $post_id );
    if( empty( $post ) ) {
        return $permalink;
    }

    // Get taxonomy terms
    $terms = wp_get_object_terms( $post->ID, 'tax_states' );   
    if( ! is_wp_error( $terms ) && ! empty( $terms ) && is_object( $terms[0] ) ) {
        $taxonomy_slug = $terms[0]->slug;
    } else {
        $taxonomy_slug = 'united-states';
    }

    return str_replace( '%tax_states%', $taxonomy_slug, $permalink );
}
add_filter('post_link',      'state_permalink', 10, 3);
add_filter('post_type_link', 'state_permalink', 10, 3);

Finally, I have these custom rewrites in place:

/** Rewrites to allow our permalinks to work **/
/** This fixes `/listings/%tax_states%/` **/
/** This fixes `listings/%tax_states%/property/post-title/` **/
function type_tax_rewrites( $rules ) {
    $new = array();
    $new['listings/([^/]+)/property/(.+)/?$']   = 'index.php?cpt_listings=$matches[2]';
    $new['listings/(.+)/?$']                    = 'index.php?tax_states=$matches[1]';

    return array_merge( $new, $rules ); // Ensure our rules come first
}
add_filter( 'rewrite_rules_array', 'type_tax_rewrites' );

Since all the above works besides pagination I feel like I’m doing something wrong here. I almost feel like WordPress should be handling the rewrites and I wouldn’t need to rewrite every scenario.

I’ve printed out my $wp_query in a template_redirect hook to see what the Query Variables are and these stuck out:

[tax_states] => 2,
[paged]      => 0,

So, tax_states is taking the paged variable and I’ve been playing around with rewriting it but I am unfamiliar with how the rewrite system works and as I’ve stated above it just seems like I’m doing something wrong if I even have to rewrite for pagination. Here’s the rewrite combinations I’ve appended to the above rewrite_rules_array hook:

$new['listings/page/([0-9]+)/?$']  = 'index.php?paged=$matches[1]';
$new['listings/page/([0-9]+)/?$']  = 'index.php?tax_states=$matches[1]';

Neither of the above seem to do anything different, pagination still leads to 404s.

The Core of My Question Is

1. Am I doing the permalink tag correctly? Is there a better / easier way to do it?
2. How can I fix pagination and keep the permalink structure described above?

Thanks to Milo’s help the code in the question ended up working: permalinks fixed and the structure stayed exactly how I wanted it described in the question above.

1. Removed the rewrite_rules_array hook entirely
2. Moved my taxonomy registration above my post type registration
3. Changed the taxonomy to be non-hierarchical 'hierarchical' => false

From my limited understand of how it works based on what Milo was describing is that the built-in WordPress rewrites that handle Hierarchical Taxonomies interferes with the structure I was trying to achieve, I can only assume because of /parent-term/child-term/ rewrites. The built-in tag already achieves the structure I was going for which is why non-hierarchical end up working.