Hi Johnno, good work on the kegs!
Firstly, as you said you'll probably want to change the orings on all of them first up. You might as well do it from the start regardless of the condition of the orings already on them. You can get the oring kits from most HBS, I know Craig Deacon sells them for $9.95, I got mine for $3A from RCB equipment.
Secondly, look for major dents in them that may have gone so far as to hole the kegs. Dents are usually no more than cosmetic and you would expect all kegs to have some minor dents, also look for welding/patching jobs. Then make your judgement.
Thirdly, what parts do they need? This is the part to be wary of. Buying spare parts for these kegs here in Australia can run you well up over the price of a whole keg. I got three kegs for a very good price that needed various parts including posts, pressure release valves, poppets and diptubes. I had gotten prices for the parts from RCB equipment before I bought them so I knew what I was up for. I found that RCB had the best prices for parts, send them an email because they don't show all the stuff they have on the web. Or send me a pm. I have bought all the above parts so can give you prices. Shipping is 5/8th's of FA for keg parts.
Fourthy, if you have the option get kegs of all the same make. This makes buying parts alot more simple in future and when you clean them you don't run the risk of mixing up parts. It's no problem once you know how to distinguish the different makes/model and what parts fit which but if you have the option to get all the same then do it. The common makes of ball lock kegs are Firestone Spartanburg Challenger V or VI, and Cornelius. If the kegs are labelled Coca cola, then they are probably pin lock. The firestone and cornelius can also come in pin lock as well I think but thay are less common. If the kegs are missing fittings as above try to play about with the different parts to get as many parts as you can for the right kegs.
Fifthly, most stains and gunk can be removed by caustic soda or an acid based cleaner. These chew through the crud and you would be surprised what they lift. So unless they look absolutely terrible (and/or rusty inside) you should be fine.
Good luck. You'll love life with your new kegs.
JD