Custom Permalink Tag breaks Pagination

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.