Paginated table displays are not a feature of the core
JSF tag set. So presumably you are using an extended tag set such as RichFaces, IceFaces, or PrimeFaces.
Exact details vary, depending on which extended tag set you use, but there should be a "page number" property that assists the pagination. You'll need to reset it.
The secret of how to be miserable is to constantly expect things are going to happen the way that they are "supposed" to happen.
You can have faith, which carries the understanding that you may be disappointed. Then there's being a willfully-blind idiot, which virtually guarantees it.