Deleted hosts don't stay deleted

I have some hosts where the domain name changed, creating duplicates.

I delete the duplicate host (which has not reported in a week) using either:

Patchman-->Hosts --> Delete
Django administration --> Hosts --> Delete

and after some time, the host re-appears.

I've also tried deleting all reports for the host, but this doesn't make any difference.