I think you should just do get your CO2 refilled. I mean, you almost answered your own question - if you haven't used the kegs in a few years (presumably there was wear on the keg system before then) then it definitely sounds like you've got a CO2 issue. I wouldn't consider a once-every-three-years $21 (MUCH cheaper, some places) refill cost as to be wasting money by any tight-wallet'ed perspective.
Fill up the gas....or I'll pay for shipping for all your unused keg equipment!!!!