Check the poppets out. If they're nasty, just replace them with new ones. I'd give the kegs a good hit with hot PBW solution (mix up about 1.5oz per gallon of hot water) and let it soak for a few hours. Shake it up in the kegs initially, and then after about 20-30 minutes of soaking. Put enough to go over the fill level of what was sitting in the kegs.
I agree with replacing all the o-rings too. You can also run the hot PBW solution through the liquid tube, and use a brush inside it (to get any really nasty stuff out).
IF PBW won't get the kegs cleaned, with a bit of brush work, then you could try some citric acid solution. I've used that to remove oxidization from metal before. Mix that up hot too.
For parts, I'd check with Keg Connection first... Without knowing where you are located, shipping could be pretty fast (rates are typically very reasonable).