Thank you, that helped a lot. I think I have found the issue.
It looks like, that the attachments search was causing the problem. For some reason the attachment result objects were filtered from the results page, however the results counter remained the same, thus the page count was calculated incorrectly. The theme might have a filter of some sort of removing those objects, I am not sure. Anyways, I have disabled the attachments search, now it should be okay.