The first step I would take is inventory. I've started a number of labs, even created recall databases from scratch. First you need to know what you have to work on. If you have a database, make a print out of the database (manufacturer, model, serial number, identification number (if you use a separate one), last calibration date, next due date, location, owner.
Using the database printout (or electronic version if that works for you), divide it into logical sections either by department, location, equipment type, or what ever makes sense for you. Then ask people from each area to inventory their equipment. Ask them to check off everything they find, and ask them to verify the information (make sure you have all correct information on each instrument). Ask them to add any additional instruments not on the list, and ask them to identify any instruments already on the list that they can not locate.
You may actually find that some instruments have moved to other locations. So cross-check between lists to make sure that missing items from one list are not on another list as added instruments. Once you have a final list (including missing instruments), make sure that the appropriate management is aware of missing items. Perhaps they are locked in a cabinet somewhere.
Once you have an accurate list of what you really have, then you need an action plan for how to get everything calibrated.
The following steps are not necessarily in order of priority, just as my brain thinks of them:
1. What needs to be sent to outside vendors for calibration. Take that list and determine where you are going to send those items.
2. What do you have to comply to? Sounds like ISO9001. Are there instruments that are the most critical to conforming to ISO9001? Prioritize those.
3. Are there instruments that directly impact product quality or whether it will meet specifications? Those instruments should take a high priority.
4. Are there instruments that impact safety or environmental hazards? Those should be given a priority.
5. Your lab standards. Before you can calibrate anything internally (if you do in-house calibrations) you will need to get your lab standards calibrated.
6. If there is a pressing need to get everything calibrated very quickly, you could also consider hiring an appropriate lab to either come in-house to calibrate everything (or most of it), or get bulk, expedited pick-up service from an appropriate lab.
7. If you can not afford to have everything gone or calibrated at once, consider making strategic decisions about which items to be sent out at a given time.
8. Try to identify broken instruments, if possible. There is the possibility that some items are inoperative, and may not be worth the cost to repair.
I came into a company of 200 employees with about 1000 un-calibrated instruments. There were about 125 broken instruments. I self-taught myself how to do a particular repair in-house (the attenuator assembly on an H-P 8640B RF Signal Generator), so that it met mfr's specs. It would have cost the company $2500 each, and there were 60 of them. I saved the company >$100,000 over the course of the six months it took me to repair them, and used that to justify purchasing an H-P 8902A Measuring Receiver for about $35K. Think about strategic decisions, such as, what can you calibrate in-house more cost effectively (if you have the right skills) than sending out. Use these cost savings to justify expanding your lab capabilities.
If you don't have automated software to perform calibrations using GPIB, consider whether your workload may justify that. I won't include any brand names, as this is a non-commercial site.
There are probably plenty of additional ideas to help you get started with this. Hopefully I have given you some starting ideas.