No sweat if you can't find them, you'll just get all the shots again. Obviously it's easier on you if you can find them, but the only reason to have them is to save yourself getting the shots again.
Not entirely true. Corpsmen love to pull that, it's happened to everybody, including me. But talking to some doctors, apparently there are certain vaccines you should not get more than scheduled (i.e., X times in adulthood or every Y months); it can compromise the immunizaton efficacy or cause medical problems. Make every effort to find or re-create your vax record, and sanity check it every time you're told you need a shot again.