After your reply, I did a little more testing. Using a where clause on any other field on that layer works fine, e.g., "PIDN <> ''". Also changing the where clause to "Shape_Area > 0" returns all 5137 records. Using "Shape_Area>0" (no spaces) returns only 1000. Does the server cache queries? I ran the query with no spaces in the where clause before changing the MaxRecordCount to 10000.
The server version is 10.1.0 (build 3035). Not sure if that is SP1 or not.
Thanks,
David