Thanks for your replies.
galigeo -I'm using ArcGIS 9.3.1.
rscheiltlin - You got it! I misread the article that your previous post pointed to. I only restarted the map service, not the SOM. Thanks so much for your help! So, for others who are looking for an answer:
To change the number of records returned by a map service. Go to the config file location; by default this is at:
C:\Program Files\ArcGIS\server\user\cfg\
open the cfg file for your service with a text editor (like Notepad); these are named by the follow pattern:
<configuration name>.<service type>.cfg
find <MaxRecordCount>500</MaxRecordCount>
Change the 500 to your desired value.
save the file.
restart the ArcGIS Server Object Manager service, (Control Panel -> Administrator Tools -> Services)
Thanks again!