Mark,
Where in the 'Midwest' area are you referring to? Quality Calibration Service in West Allis WI, 1-800-285-0035, performs CMM calibrations on many makes of CMM's. You might want to try them.
A new company that I have been working with CMM Calibrations out of the Chicago area may do Zeiss, but I am not sure. Their phone number is 630-801-7961. I do have other cards for CMM calibrations if you want to give me a call at 847-742-0700 X2477.
As for the requirements for A2LA, NVLAP, IEC 25, certification; it has been put on hold until after mid 2000. Seems there are not enough calibration services that meet the requirement so the wavier was given. The company you select should be at least have a plan to get accreditation.