A recent discovery of a “feature” in Microsoft Reporting Services reports is that when you toggle visibility for a report element, for example, a table inside a rectangle, then you’ll find that paging on that element no longer works.
This is exactly what happened in a recent report where I toggled visibility of the grid in the event that there is no data and displayed an alternative friendly message instead from a separate rectangle with the opposing visibility expression. In my case, this became evident when I used the ReportViewer component on the page already heavy with content and it took ages to render a report.
Unfortunately this is something in the box and thus not bypassable. See the thread here.
Thus the only option is to turn off the visibility expression…