When you recreated/killed the VMs the effect is similar to the one which will happen in case you directly remove the network connection of a shared agent. The shared agent will not notify Jenkins that the connection is off so Jenkins continue thinking that there is still a connection alive with this shared agent. Jenkins uses the ping thread in order to kill a connection when there is not an answer back from an agent after 4 minutes by default.
In case ping thread is disabled with '-Dhudson.remoting.Launcher.pingIntervalSec=-1' the OS will kill the connection after a timeout which depends on the OS.
So in case you restart the VMs, the connections will be re-created, but the IDs of each shared agent will be different even if the name of the shared agent is the same. Notice that agents are identified internally by IDs and not by the name we use when declaring them on Jenkins GUI.
To avoid this, we recommend:
Quitting the JNLP agent on the client - just make sure the OS is up long enough to send the TCP SYN and get it acknowledged.
Taking the shared cloud/shared agent to a "offline" status from the GUI would at least make sure that they where not picked up whilst terminating (or picked up when they are dead).