Pagination doesn't work quite right with nginx caching

I’ve been using pagination on a few post types, and it seemed to be fine for a while, but recently I’ve noticed that if I’m not logged in (so the normal page view, cached by nginx), the pagination doesn’t actually show older entries when you select previous pages of posts. It just shows the most recent ones on all the other pages/lists.

If I purge the cache, and then watch as it caches again, it seems fine (cached and uncached) - but at some point, it will stop working correctly again and the cached page will just have the same list on all previous post pages.

Any thoughts what’s happening here?