After deleting the Availability Group, we will need to remove the nodes from the WSFC Cluster by uninstalling WSFC Service (instead of destroying the Windows Cluster which cannot be possible in this case). Having accomplished that, we have to create the Windows Cluster again and then add each node. Finally, we are going to be able to set up the AlwaysOn Availability Group. Ideally, it is the normal procedure for it.
Nevertheless, we cannot play by the procedure as each case is particular (and this case really is). It might not be a great surprise if we get this error when setting up the AlwaysOn Availability Group:
Obviously, this error is due to an incorrect uninstallation. Luckily, this can be fixed by disabling the AlwaysOn Availability Groups feature at a database engine service level.
We now have to enable it again and then restart the database engine service.
Not until you have done these all steps will you be able to create the Availability Groups again. Thanks for reading again!