Using a query from REST to generate a KMZ file returns all records, where HTML and JSON perform as expected in ArcGIS Server for the Microsoft .NET Framework 10.0 Service Pack 5.
This issue is not reproducible in the current release of the software. Contact Esri Technical Support (for customers in the United States) or Esri distributor (for customers outside the United States) to resolve this issue, if the issue persists.