Ive run into this issue multiple times now. Here is the situation:
At this point, if Altiris does its thing correctly and merges the new record for the RS server with the old one (retaining the old GUID), you will not be able to add the rebuilt RS server to the cluster as Altiris still thinks the original server is still servicing that cluster (basically, since the new RS server takes assumes the old GUID, Altiris thinks that nothing has changed and that the old server is still out there servicing the cluster). You can verify this is the case by opening the “Recovery Solution Server Uninstall” section on the Notification Server console. In there you will see the server that you rebuilt as available to uninstall (even though the rebuilt server doesnt have the RS server installed on it yet).
This leaves you with a unique situation…you need to remove the RS server record from the cluster to make Altiris think there are no RS servers servicing that cluster so that you can install a new RS server into that cluster (the rebuilt server). This can be accomplished by removing a row in the Notification Server database:

At this point, you will now notice that this server no longer shows up in the “Recovery Solution Server Uninstall” area in the NS console. You now will be able to add your rebuilt RS server to the cluster.
Tags: altiris, Recovery Solution
Haha am I actually the only comment to your incredible post?!
Hehe am I really the only comment to this awesome writing?!?