Thanks for the reply.
This occurs for Images and documents.
Using the steps you described I get the results that I have described.
The system is an upgrade from 3.5 to 3.7 SP4.
The only customization we had for that Module was to create better caching of the data under 3.5. i.e. Not having the full object graph for the Libraries loaded on every page of the pager.
I've removed this custom logic and removed removed all redundant views.
The only external template is the LibaryListView, which I have implementated some search functionality on.
Apart from that it's stock standard.
Could the previous issue be related?
That is could the actual data be causing this issue.