Hello,
the SEP registration and communication is protected by using encryption key and security certificate, these are unique of each SEPM installation, this is for obvious security reasons. Being able to re-create the old security certificate is not technically possible and it would be a huge security hole.
When you reinstall the SEPM without restoring any backup, encryption key and security certificate are different than the previous installation and SEP agents can't know them, there's no way they register into a SEPM if they are not told how to do that (i.e. knowing new SEPM's key and certificate).
Those things are locally stored in the SEP agents, in the sylink.xml, this explains you why you need to replace that file on all clients, no workaround.
If you can't "just" replace the sylink.xml on the clients, you have to reinstall the SEP agents (but if you can't replace a single file or run a tool remotely on multiple machines due to the exposed IT management limitations in your network, I doubt you can reinstall any software on 1000 clients in a comfortable way).