http://msdn.microsoft.com/en-us/library/windows/desktop/aa746414(v=vs.85).aspx
"you must use a paged search if there is the possibility that the result set will contain more than 1000 items."

...

"It is recommended that paging is used."

I think we should always specify a page size if none are set as these issues then go away.

In your environment try doing user enumeration on users without a page size (as your computer dont number in the 1000s). 

N.B. I no longer have access to domain :(