I have played around with the search, trying to get the search query which would break the paging - but all of them were working fine for me.

Can you, please, paste the URL which is causing messed pages?