Overview

Short Answer, Don’t start fresh.

If in a clustered topology with a dedicated CMS. Remove from topology,  add new server with new name to topology and redeploy fresh.

My Expereince:

Step 1) Restore LyncVM created on resource domain, change hostname.
Step 2) Stop All Lync Services
Step 3) Create SRV record for _sipinteraltls, and 3 a records (admin, meet, dialin)
Step 4) Remove old CSM, else topogly deployment will fail. (Remove-CSconfigurationStorelocation)
Step 4.1) Extend Storage to 80Gig, else publishing will fail. (https://docs.microsoft.com/en-us/skypeforbusiness/troubleshoot/server-install-or-uninstall/error-when-install-lync-server#:~:text=This%20issue%20occurs%20because%20the,16%20GB%20of%20free%20space.)
Step 5) Open Topology Builder, if host name same, open file, if new host create new topology. Publish
FAIL

Step 1) Cloned Server
Step 2) Removed from Domain (disconnected)
Step 3) changed Hostname, and joined Domain
Step 4) Run Deployment Wizard -> Prep First Standard eidtion server
Step 5) Run Deployment Wizard -> Setup or Remove Lync Components -> Step 2
FAIL

Step 1) Cloned Server
Step 2) Removed from Domain (disconnected)
Step 3) remove all local SQL instances
Step 4) Delete C:\CSData
Step 5) Rename, Join Domain
Step 6) Run Deployment Wizard, Prepare First standard edition server
Step 7) Adjust DNS (_sipinternaltls, admin, dialin, meet)
Step 8) Remove-CSConfigurationStoreLocation
Step 9) Create and Publish Topology
SUCCESS
However Install CMS: failed:
https://social.technet.microsoft.com/Forums/en-US/88fc3dc6-cf74-474e-baf7-08609211ac1b/cannot-open-database-quotxdsquot-requested-by-the-login-the-login-failed-login-failed-for-user?forum=lyncdeploy

Long Answer (Source): This info has been shared on many blogs, not sure who’s the originator of the list

1. Remove Skype for Business server from topology
2. Publish topology.
3. Run Skype for Business Server Deployment Wizard local setup on server to remove Lync components (or run the bootstrapper)
4. Uninstall SQL Server. Front-ends have LyncLocal and RTCLocal instances. Remove both, rebooting between instance removal.  Edge only has RTCLocal instance.
5. Remove SQL Server 2012 Management Objects (x64)
6. Remove SQL Server 2012 Native Client (x64)
7. Remove Microsoft System CLR Types for SQL Server 2012 (x64)
8. Remove Microsoft Skype for Business Server 2015, Front End Server
9. Remove Microsoft Skype for Business Server 2015, Core Components
10. Delete leftover data:
    Delete C:Program FilesMicrosoft SQL Server
    Delete C:Program FilesMicrosoft Skype for Business Server 2015
    Delete C:CSData
11. Rename server and restart
12. Wait until AD replication completes with new server name.
13. Open Topology Builder, add a new server to existing pool and publish. (If this is a SBA or Standard Edition Server, the pool and the server FQDN is identical.)
14. Reinstall Skype for Business Server 2015components and all cumulative updates
15. Generate new certificate with updated server name and assign to appropriate services using Skype for Business Server 2015 Deployment Wizard.
16. Restart all servers in pool at same time (only relevant for front-end servers in an Enterprise pool).

Summary

Don’t do it. It’s so much easier to start fresh then deal with this garbage.