Does the new part have the same name/number as the old part?
Was the old part used as the base model for the new part, or was the new part started from scratch?
How large are the assys? Can they all be opened at once, or maybe in just a few batches?
No the new part does not have the same number as the old. This question is being asked preemptively, so the new part can be made either way if one method is advantageous. The assemblies would probably have to be opened individually due to the number of configurations.
Check if SOLIDWORKS explorer can help you.
It does make a difference. I would try.
Check out the part you want to be replaced.
Rename your new part to the old (outside) the vault.
Paste on your old file.
Now your assemblies will use your new part. After checkin you can change the name of your new part back to the new name if you want. What you might consider a downside, your old part will be gone and history will be in the "new" part..