The latter pages of pagination show a 404 on the search page, but on the custom taxonomy pages of the same tag, all pages work properly.
I was completely lost until I saw the title of the search results:
Although it shows 32 pages of results, wordpress (the title) says there are 28 pages!
Sure enough, after page 28 is where you get stuck in the twighlight zone of 404s.
As mentioned though, this does not happen navigating the same tag on the taxonomy pages - just search.
Any idea what causes this generally? WordPress is not playing nicely with my custom post type.