I understand you as asking something along the lines of "if we can't produce the PQR's that support our WPS's do we have to do the PQR's over?" This is why we digitize them in our company, they can't be lost to earthquakes, fire, flood, or thieving knaves with proper backup procedures in place. To more directly respond though, yes I would say you have to replace them, understanding that your WPS's were qualified by testing. How frantically you go at it depends on your business. If you are a OEM, procedures hardly enter into obtaining new business, they are more a bulwark against the rainy day when 40 Philadelphia lawyers write you a letter of concern about some aspect of alleged negligence in the design or manufacture of your product. If you are a construction contractor, telling the general or the owner that "We had all these WPS's and supporting PQR's but we just can't locate them." is probably not going to get you any new contracts. Conversely, though, if you are in a business that has to regularly submit WPS's, it may be much easier to replace them. Simply see if some of the customers you submitted to retain complete copies and ask for a copy. The lab we contract retains their reports indefinitely, and for many of the procedures at my present company, that includes the WPS and the PQR, we only moved to a model of actually writing the WPS's in house over the last couple of years.

Good luck in recovering your documentation.