You’re experiencing what is intended; using the nextPageToken, you can only get up to 500 results. If you’re interested in the development of how this came about, you could read through this thread:
https://code.google.com/p/gdata-issues/issues/detail?id=4282
But as a summary of that thread, it basically comes down to the fact that, with so much data on YouTube, the search algorithms are radically different than most people think they are. This isn’t just just doing simple database searching for content in fields, but there are an incredible number of signals that are being processed to make the results relevant, and after about 500 results the algorithms start to lose the ability to make the results worthwhile.
One thing that has helped me wrap my mind around this is to realize that when YouTube talks about search, they are talking about probability rather than matching, so the results are ordered, based on your parameters, in terms of their likelihood to be relevant to your query. As you paginate through, then, you eventually reach a point where, statistically speaking, the probability of relevance is low enough that it isn’t computationally worth it to allow those results to come back. So 500 is the decided upon limit.
(Also note that the number of “results” isn’t an approximation of matches, it’s an approximation of potential matches, but then as you start to retrieve them many of those possible matches get cast aside as not being relevant at all … so that number doesn’t really mean what people think it does. Google search is the same way.)
You might wonder why YouTube search functions in this way rather than doing more traditional string/data matching; with so much search volume, if they were to actually do a complete search of all the data for every query, you’d be waiting minutes at a time if not more. It’s really a technical marvel, if you think about it, how the algorithms are able to get such relevant results for the top 500 cases when they’re functioning on prediction, probability, and such.
As to your second question, the page tokens don’t represent a unique set of results but instead represent a sort of algorithmic state, and are thus pointers to your query, the progress of the query, and the direction of the query … so iteration 3, for example, is referenced by both the nextPageToken of iteration 2 and the prevPageToken of iteration 4, but those two tokens are slightly different so they can indicate the direction they came from.