Are there sub-folders in those paths? If not you are in luck - just add the new paths to the search paths in SolidWorks. It will look there first.
Look up Search Routine for Referenced Documents in the Help - it will explain it better.
If there are sub folders - you will need to add in each sub folder path.
A PDM system would help you moving forward but this should get you back up and running.
Thank you kindly for the remarks, Jenny. In one of the library paths, I have a directory structure which looks like:
It would be rather painstaking to add all of these sub-paths manually. The other two directories mentioned above are less complex, I could easily add all of the sub-folders manually. I'll look into the help documentation (here) you mentioned. Maybe the manual work involved is enough to justify moving to a PDM.