That is entirely possible. You didn't specify how you're actually paging but I'm assuming you're using the returned nextLink
value. Users aren't "frozen" during enumeration so depending on the ordering it is possible to get back the same user on multiple pages because of changes in the user list. Note that the next link should have a skip token which should ultimately reduce the likelihood of this happening as it generally (based upon other APIs) is an encoded version of the query that the server uses to fetch the next set of results. However if you change any data going into the search then this invalidates it. Even then though it is possible to have dups. But ideally if you could provide us a repro so we can see what you're doing and the results you're getting it would be easier to identify if you're doing something wrong.
Personally I would use Graph Explorer and run the same query. If you get dups across pages then the API is returning dups. If it doesn't return dups then it is more likely your code.