GData API navigation is limited to TOP 500 results (e.g. you cannot navigate more than 10 times assuming 50 results per page)

The number of results you tube API is providing (potentially also all other GDATA) is an estimation and as such if you got totalResults = 4000 , the API will only allow you to get the first 500 (and not w/a for it).
When iterating on the next page, you will see that on the 10th page (assuming 50 results per page) the nextPageToken will be null.

The main reason is that the API is estimating and also ensuring quality of search for the first segment

So if you need to get more than 500 results, suggest you partition the queries in some way

See here for original post