Michael M.,
My advice would be to find a lab that can actually check all parameters, to the required tolerance, with adequate measurement uncertainty. This is assuming you actually want thread gages that meet ASME requirements.
Most labs that I know of use a supermicrometer and wires to check pitch diameter, and a supermic to check major. Most often, this is a Pratt & Whitney Model C. If one were to perform an uncertainty analysis for thread measurement with a supermic, I'm guessing you would come out in the >=(?0.000050")
Keep in mind that your smaller gages will have a tolerance of 0.0002" on pitch diameter. (Plus or minus, depending on whether it is go or no go.)
Here's a quick look at my guesses for two major error sources:
Thread wires (?0.000020") They are called out tighter than this, but only if you have the capability of checking them. Most labs follow the allowed alternate method of using a master thread wire which they compare their working wires to. The master wire is supposed to be within 0.000005". Check measurement uncertainty on a cal cert for a master wire and see what you are actually getting. Then, the working wires are compared to the master wire using, you guessed it, the supermic. (resolution is 0.000010. Repeatability/reproducibility will not be better than 0.000020, from my experience.)
Supermic (?0.000020") When measuring plain diameters. Throw in three wires over a threaded gage member, and how bad this gets is dependent upon the care taken by the tech, tech experience, and tech training.
Now, if you actually want K=2 or higher, then the ?0.000050 could be higher.
Then, most labs use an optical comparator to measure other parameters such as lead and angles. Once again, perform an uncertainty analysis on an optical comparator and see what you get. Just make sure that, for the data collection portion of the analysis you use actual gages, not glass scales.
So again, I would recommend you be very, very careful in who you select. Labs that do this correctly use something like a Pratt & Whitney LMU or Mahr ULM for pitch and major diameters, then a lead checker for lead. (It is possible to measure lead with the P&W LMU, but I haven't done so in years. Extremely time consuming and, from a commercial lab, would be very expensive.) Going from memory, angles are a relatively wide tolerance and optical comparator may be okay. It's actually been a while since I've looked at this, so I can't quote all of the tolerances off hand.
If you want more information, send me a private message and I'll be happy to share anything I know. I spent a lot of time dissecting threads, verification methods and equipment, and requirements. This included talking to a couple of the ASME standards committee guys who are currently working on revising the standards.