Custom permalink settings break pagination for pages 2, 3, etc.

If I change my permalinks (WP Admin -> Settings -> Permalinks) to default (i.e. site.com/?p=123) my pagination works fine. But if I change the permalink to a custom structure (e.g., site.com/%category%/%postname%/) then pages 2, 3, etc. don’t work.

Here’s an example of how the url comes out when doing a search:
Page 1:
site.com/?s=training (WORKS)
Page 2:
site.com/page/21622/?s=training (Nothing Found error)
Page 3:
site.com/page/3-long-term/?s=training (Nothing Found error)

It looks like it’s querying pages that start with the page number instead of pulling the correct 2nd and 3rd pages.

When I disable all plugins it still doesn’t work properly but instead of giving a Nothing Found error it just redirects to the 1st page of the search.

I already tried disabling canonical redirect but that did not work. Any help would be greatly appreciated.