"Remove hosts" only partially removes host

[Jesse]

I have an auto discovery rule that finds hosts that have been down for a certain amount of time and attempts to remove them. When the rule is matched it does a "Remove host" as well as issuing some remote commands to remove them from other services. This all works pretty good except the "Remove host" doesn't seem to fully remove the host. It does successfully stop monitoring it, however, when the discovery rule runs again it triggers the actions and runs all the remote commands again. This is undesirable.
What can I do so that the host gets fully removed and does not trigger the discovery rule again?

Thanks.