QA vendor evaluation

I haven't done this either. However, I've responded to numerous RFPs that have requested services along these lines. I'd summarize some key points about them:

Generally, they ask for multiple references for clients/engagements with properties or aspects similar to the company/project procuring the services. They also ask for a detailed description of the methodology to be used. A Project Management methodology description is also frequentely requested. Resumes of key staff are generally required, and these can be specified to be the exact staff that will be assigned to the engagement, or alternatively can be permitted to be representative of their staff as a whole. Also, a general description of corporate background, experience in this area (particularly in similar engagements) and a general organizational ability to deliver (which can include financial soundness) are usually required. Consider asking about Service Level Agreements (SLAs) that have been implemented in the past.If I were in your shoes, I would use these categories as a guide to evaluating these firms. I know of no specific industry-wide metrics that apply, but some specific subject matter metrics might apply. In saying this, I assume that your QA requirements are, in fact, Quality Assurance related, rather than Testing related. If not, there are many sources of information about performance measures related to testing: try amazon.com for books on software testing.

I know this isn't entirely responsive, but I hope it helps a little.

There is no set of metrics that can be used for this. Comparision is the best way out. Send out RFI's to firms you shortlist.
Send them a high level description of what is expected of them and review their interpretation of your problem - compare each ones interpretation!
The best way is to check the vendor's capabilities. Check profiles of personnel.