Normally services are configured by default to return only the first 1000 records. You can change the configuration of the service to return more features or if you don't have access to this configuration you can use for instance the REST interface to query records based on for instance the ObjectID:
objectid > the highest objectid from the previous query.
The query below queries the features starting from a certain objectid:
Query Features (Earthquakes from last 7 days - Earthquakes/EarthquakesFromLastSevenDays)
Using some Python code you can translate the url query to a featureclass:
import arcpy
fcout = r'path to your output featureclass'
url = 'http://sampleserver3.arcgisonline.com/ArcGIS/rest/services/Earthquakes/EarthquakesFromLastSevenDays/...'
fs = arcpy.FeatureSet()
fs.load(url)
arcpy.CopyFeatures_management(fs, fcout)
You should start with querying the entire service, store the result as featureclass, determine the highest objectid, and use that objectid in the next query. At the end merge the featureclasses...
Kind regards, Xander