YouTube imposes a soft limit of around 500. There is no direct way to get more than through the API.
Full details: https://code.google.com/p/gdata-issues/issues/detail?id=4282
Appropriate exposure:
"We cannot provide more than 500 search results for any arbitrary YouTube request through the API without compromising the quality of search results (duplicates, etc.).
The v1 / v2 GData API was updated back in November to limit the number of search results returned to 500. If you specify a starting index of 500 or more, you will not get any results.
This was also supposed to take effect for API v3 (which uses a different method of paging through the results), but it did not seem to be popped, so you can still get up to 1000 search results in v3 - the last 500 of which are usually have poor quality.
Changing the limit of search results from 3 to 500 will be supplanted in the near future. There will no longer be nextPageTokens if you apply 500 results.
I understand that the returned totals far exceed 500 in all of these cases, but this is not the same as saying that we can effectively return all X million possible results. This meant that estimating the total size of the video set that matches the query is generally not very useful. "
Updated - How to overcome the maximum soft limit of the result of 500
Use the filters "published" and "published" to break your query into query cycles by day / week / month, until you get more results. Each periodic query should return less than 500 results each, but you will get all of them.