Uninstalling from the old PC is not strictly necessary. What you want to do, is to DEACTIVATE (using the relevant Addon manager option), all the sceneries from the old PC *before* reformatting, when they are still active.
Doing this, will prevent consuming an activation when reinstalling on the new PC.