Very good previous reply to which I couldn't add much. But since I haven't posted in a while, I'll throw in my two cents.
You asked in terms of percentage that should cycle through the metrology lab. The two part answer is that what percentage of them cycle through the lab at a given time is based on workload management and the variables of how well the customers do at turning them in on time.
The second part is how often they should be calibrated. There are a number of philosophies on this. I would recommend checking NCSL recommended practices for the establishment and adjustment of calibration intervals. They cover the various industry-accepted methods.
My personal view is that you establish intervals between calibrations based on gage types (there are many ways to break that down). Some types might need an interval of 6 months, others 12 months, etc. Then, based on history of in-tolerance performance, adjust either individual or families of gage types based on that history. A common rule of thumb is 95% in-tolerance. You increase interval (as appropriate for your context) for better than 95%, and shorten for worse than 95%. There is some freeware available in which you can enter basic numbers, and it will tell you what to adjust the interval to.
As far as gages that do not show up when they are due, that is a quality policy issue. Depending on how strict your customer context is (FAA, FDA, QS9000, ISO, etc.), you may want to consider documentation. In some very strict contexts, any instrument that does not show up on time for cal, documentation is produced in which the issue is escalated through the management chain. If a gage is lost, appropriate management would have to sign off. And when it is eventually found, management would also need to sign off on documentation describing circumstances. The goal is to assure that past due items can not be used beyond their due date. If an item is "LOST" but in actuality it is still in use, there may be serious risk potential (in some strict customer environments). You'll have to decide how strict your environment is to decide what measures need to be taken.
I've seen circumstances in which government auditors can require that proof be given regarding"LOST" gages to assure that management has adequate control.
As it's late and I am exhausted, I'll end there. Bottom line regarding lost items etc., what is your customer quality system requirement. Based on that, I (or others here) may be able to give some inputs on how strict to be.