Solved! Go to Solution.
maxRecordCount is a read-only property which is carried over from the map service. The only way you can increase the limit is to change maxRecordCount of a map service using ArcGIS Server Manager or ArcCatalog.
Query for ObjectIds. There is no limit on the number of ObjectIds that are returned from the server.
As far as I know, the only way is to increase the limit using ArcGIS Server Manager.