1) You don't have to reinstall.
2) Regit is the worst licensing problem program I've ever seen.
regit has several important files:
a) regit.log
b) licfiles.log
c) lic98.log
d) lic98.dll
e) product.dat
Look in licfiles.log and regit.log to see if it had a problem accessing lic98.dll when you attempted to install the software or when running regit to generate the key.
The problem is lic98.dll can sometimes get LOCKED. When this happens, Arcserve holds it when you install Arcserve software or run regit, it needs to talk to lic98.dll, can't, and fails.
To make things worse, you will think the program is registered as it will generate the license key with a RC of 0, but then the program DIES in 30 days. Great...
What you need to do if this happens is to rename lic98.dll, reboot the server, recopy lic98.dll from the CD (get the correct version/date of lic98.dll!), and then rerun regit.
If you have license problems you can just rerun regit and it uses the last license key you generated with it. You should be fine as long as you use the right key for the software and regit can talk to lic98.dll.
Be certain to check the event viewer app log and logs 1, 2 and 3 above. The product.dat opens with notepad and has the product codes such as "3NUB" listed next to the friendly english names of their products so you can figure out what is not working. The knuckleheads at Arcserve seem to try and make it as difficult as possible to license anything they have.
Also be aware that the Arcserve discovery service and liccheck.exe will ping anything it can on your subnets and will discover duplicate licenses of arcserve out there. So unless you want to figure out what port it operates on and block it on the other AS servers, you need to be careful you don't accidentally dupe a license. When you have several people all playing with Arcserve, this can happen (dupes).
Good luck