Actually my problem is something like this:
My workaround was to manually set page to 1, every time number of displayed rows change. This works fine. Only if I change from page 2, to only one result page... then not all elements are displayed.
Ok. The problem seems to be in my own implemented DataModel. I followed exactly this post:
Now, Richfaces calls the walk Method with firstMethod always > 0, and so, my walk method always retrieves then firstRow (which is >0) to lastRow, which are not all elements. Element 0 to firstRow (which is >0) are not rendered therefore ...