The reason for the cluster rebuild was that the Network Name and IP address had disappeared from the cluster. This had cause the DNS host to be deleted from DNS, and therefore no connections could be made to the cluster name. The reason for this is still unexplained. I could not add the network name or IP address in as a cluster resource because powershell would complain about the resource already existing (although whilst running a Get-ClusterResource showed no network name and IP address) Subsequently I could see the Cluster Name by running Get-Cluster but when trying to drill down into some of the cluster parameters the result being return to me "Object does not exist". It was like the cluster had been destroyed but everything had remained in the cluster. I first noticed this when I was unable to live migrate VMs.
After talking to Microsoft, it was discovered that the Hyper-V database did not contain the cluster name, and the recommendation was to rebuild or create a new cluster.
Firstly, I shut down the VMs, then removed all of the VMs and then removed all of the storage from the cluster. However I could not remove the last VM. It was holding the role of the Cluster Access Point. Removing the last cluster Client Access Point from the cluster could not be completed. Although there we no other resources within the cluster, it could not be destroyed due to a cluster resource residing on the cluster. But yet no matter how many times I tried tried to remove this cluster resource, I could not remove it. Instead, once all other resources had been removed, I simply uninstalled the cluster feature from Server Manager and rebooted the server.
After the servers had the roles removed, I then reinstalled the roles and rebooted again. This time I had nothing in the cluster so I could continue.
I hit the point where I was adding disks to the servers. There were 6 volumes on the servers which were connected by iSCSI and they were appearing in disk manager across all nodes. Checking the connections in the iSCSI initiator showed that MPIO was working and indeed the volumes and mount points were consistent across all nodes. So connectivity to the disks was working and when browsing the disks I could see all of the data for the VMs.
So I created a new Cluster, checked all the network settings. Next I added the disks to the cluster. I could only add 4 disks. Although the other 2 disks were there, I could not add the other 2 disks to the cluster. After generating the get-clusterlog command after trying to add the disks to the cluster. I noticed some error messages on the disk section in the log. Although these were not a long string of errors, there was 1 error in a large list of informational messages saying that "Err [RES] Physical Disk: Disk X has invalid signature 0. Ignoring" Along with this error I had an information message: "INFO [RES] Physical Disk: Disk X is already clustered, same disk id" and then "ERR [RES] Physical Disk: Disk with device number X has lingering PR on it. Ignoring..."
So it would seem that the Hyper-V server, although with the cluster services uninstalled, had retained some cluster disk information from before and not correctly cleared this out of its configuration. After a short amount of time and further investigation I ran the Clear-ClusterDiskReservation -Disk X where the Disk number is the disk which is not being added to the cluster. You can find this in disk manager, or Server Manager/Storage Pools.
Once the reservations had been cleared, I could successfully finish the cluster configuration. One note however, if you would like the disk numbers to match to the C:\ClusterStorage directory as before, I would recommend bringing them online in order one at a time and add them to the cluster like this. This will ensure that your first volume will match to Disk 1 which will link to C:\ClusterStorage\Volume 1. Windows Server will ID the disks as they come online and if the disk has the wrong ID then you may get an instance where your old Disk one is now Disk 4 and you will either need to copy your VM configuration to the old volume, edit the xml file so the VM from the Hyper-V host can be managed and come out of its "critical" state. You can use the move command to move the names of C:\clusterstorage to a new directory.