Based on the above, and supported by the fact that the "compute host exists" checks exist for a reason (specifically, to make sure we don't remove a host with instances on it from an AZ), I'm closing this as WONTFIX. It's a minor, it's a minor issue, and trying to fix it would expose us to more risk than is worth.