This is an interesting question. The focus on service providers and the need to risk assess them has led naturally to the consideration of what criteria should be used. Of course it depends on the service provider and the scope of the control required e.g. food safety,technical requirements of the service, health and safety.
More importantly, you need to determine the risk of the activity in terms of failure to meet certain service standards. What would be the risk posed to the safety of the product and subsequent human health? For example some of the things you might consider are:
Pest Control: trade association membership, training certificates for individuals conducting the inspections, equipment and chemicals used, capacity for follow up inspections...
Laboratory Testing: Certification of the individual laboratory and tests to anappropriate Accreditation Scheme e.g. UKAS in the United Kingdom.
Contract Laundering: Depending on product risks; laundering process controls including temperatures, time, cycles. Separation in the operation...
Waste Management: Appropriate licence to handle waste including disposal channels
Training and Consulting Providers: Evidence of competency to conduct such work
The list is longer than mentioned above but if I recall correctly, the Tesco Technical Standard details criteria for specific contract service providers. It might be worth your time to review this.
George