machines deleted from the main Upstream WSUS server

I'm not aware of an easy way to restore that relationship to a WSUS Target group.

Tangential, but it might be of interest:

There are a couple of different ways you can get machines added to the proper patching groups in WSUS.

The way you describe above (Server Side Targeting) is the default where you point machines to the WSUS server via Group Policy and when they initially check-in to their WSUS server they are placed in the Unassigned Computers group.  You can leave them there or you can then move them to a different patching group.

With the other way (Client Side Targeting) it is possible to configure your machines with a Group Policy that automatically assigns the machines to a specific WSUS Target Group (so you might have a different GPO for each OU if you want them to go to different patching groups).  If you use that method, then you usually just have to set up the GPOs once and then whenever you add new machines to their proper OU it can throw them in the right patching group.

If you're interested in that, here's a link for more info:   Managing Computer Groups