Pagination only showed when no category is set in wp_query

Question

tldr: On my production site only, when I set category_name to any category my pagination does not show up. Once I remove category_name from my wp_query the pagination shows up (for all posts on my site, of course).

The code & full problem

I have a page and set it to my page template with the following code:

<div>
  <?php
    $paged = (get_query_var( 'paged' )) ? get_query_var( 'paged' ) : 1;
    $args = array(
      'post_type' => 'post',
      'post_status' => 'publish',  
      'posts_per_page' => 1,
      'paged' => $paged,
      'category_name' => 'videos',
    );
    $my_query = new WP_Query($args);


    if ($my_query->have_posts()):

      while ($my_query->have_posts()):
        $my_query->the_post(); ?>
  
        <article>
          <?php the_title(); ?>
        </article>
      <?php
      endwhile;
    endif; ?>

    <div id="my-pagination">
      <?php 
        echo paginate_links( array(
          'base'         => str_replace( 999999999, '%#%', esc_url( get_pagenum_link( 999999999 ) ) ),
          'total'        => $my_query->max_num_pages,
          'current'      => max( 1, get_query_var( 'paged' ) ),
          'format'       => '?paged=%#%',
          'show_all'     => false,
          'type'         => 'plain',            
          'prev_next'    => true,
          'prev_text'    => sprintf( '<i></i> %1$s', __( 'Newer Posts', 'text-domain' ) ),
          'next_text'    => sprintf( '%1$s <i></i>', __( 'Older Posts', 'text-domain' ) ),
          'add_args'     => false,
          'add_fragment' => '',
        ));
      ?>
    </div>
</div>

My 1 post shows up as expected (FWIW I have 33 posts in the Videos category), but the pagination does not. If I increase posts_per_page to 30 then I see 30 of my Videos posts but no pagination.

I tested this out in my local development environment and it works as expected.

Debugging steps

Some steps I've taken to debug:

• Exported my production database and imported it locally into a fresh install as well as imported all my files from production to local and I still do not see this issue locally
• Downgraded WordPress from 6.1.1 to 6.0.3
• I tried using wp_reset_query and wp_reset_postdata
• Tried disabling plugins 1 by 1
• Tested using the Query Loop Gutenberg block. This exhibits the same issue: as soon as I add a category filter the pagination disappears

Ask

How else can I debug this production only issue?

Update 1

Output of var_dump($my_query->request);

SELECT SQL_CALC_FOUND_ROWS wp_posts.ID FROM wp_posts LEFT JOIN wp_term_relationships ON (wp_posts.ID = wp_term_relationships.object_id) WHERE 1=1 AND ( wp_term_relationships.term_taxonomy_id IN (31) ) AND wp_posts.post_type = 'post' AND ((wp_posts.post_status = 'publish')) GROUP BY wp_posts.ID ORDER BY wp_posts.post_date DESC LIMIT 0, 1

Update 2

Update 3.5