We don't want deleted vms to live in etcd forever, but having some history/indicator that they were once there and are now gone is probably useful. One way to manage this would be to set the /booted/{instance} key to something like 'deleted', with a ttl (via a lease) of a day or so.
Then that could be queried if desired.