In ArcGIS 10, the default number of features returned by an ArcGIS Service for queries (identify/find/query) is 1000, though yours could have been set to 500. You will need to change the service properties in order to increase the maximum number of results. You can do that by stopping the map service, going to Service Properties - Parameters tab, and setting the Maximum Number of Records Returned by Server to a suitable value. Be sensible about the value though - your browser will not appreciate having 10,000 records returned along with their geometries.
Alternately you can configure the maximum number of records by changing the map service config file directly and restarting the service. The config file can be found in Program Files\ArcGIS\Server10.0\server\user\cfg and will be named ServiceName.MapServer.cfg. You will want to update the MaxRecordCount node.