Here's the scenario of sending the blocks in for calibration. The cost is $100 or $200 or whatever, I don't remember. They do a fair job of cleaning and conditioning the gage blocks so they can inspect them. If, after this cleaning, the gage block doesn't wring, they simply don't check it, or they'll measure the block and note that the gage block doesn't wring on the calibration report, therefore the measurement uncertainty and traceability to NIST is not valid. Then, you're going to ask them to provide you a quote for replacement or repair to complete the set. They'll probably provide you with a couple options, like replacing the missing blocks with import ones, etc.
Calibration labs vary widely in the price and detail of their service. I'd try to find a friendly and helpful calibration lab nearby and they'll give you a taste of what the service is likely to cost, even over the phone. I got a feeling that a good cal lab would be willing to look your gage blocks over before doing any service, and give you some kind of estimate.
Here's a link to a calibration lab in Wisconsin that explains their procedure for calibrating gage blocks.
http://www.qualitycalibration.com/gageBlocks.asp
If I remember, the bare calibration of an 81 pc set was about $180 for grade AS-1.
You could also contact Starrett, which will probably charge an insane amount for their service.
http://www.starrett.com/pages/442_calibration_repair.cfm
Take a look at this, too.
http://www.use-enco.com/CGI/INLMKD?SIITEM001=SA630-4120&SIQTY001=1&SICOUNT=1
It might seem unsavory, but why not buy Chinese gage blocks? Quality Calibration in Wisconsin offers calibrated sets of import gage blocks that they have found to be of good quality. Their 81 pc set was like $400 for grade AS-1, complete with inspection report. Then you have new gage blocks that wring beautifully and aren't cratered or dented at the corners, complete with calibration certificate.
In my hands, gage blocks age poorly. I'd rather have a new set every 5 or 10 years than a name brand set that costs $2000 and figure out how to keep them in pristine condition for 40 years.