According to this page: http://forums.esri.com/Thread.asp?c=158&f=2396&t=293222
You do the following:
1. Increase the value for MaxRecordCount tag in the configuration file for the service. The default value is 500.
http://webhelp.esri.com/arcgisserver/9.3/dotNet/cfg_file_service.htm
2. You have to restart the ServerObjectManager service from windows services panel for this to take effect.