The wmf_decommission_host.py script has a clear race condition given that the puppet crontab that runs every 30 minutes will run apt-get update in any case (also if puppet is disabled) that will re-populate DebMonitor for that host.
Given the frequency of this crontab is pretty easy to incur into this race condition.
The same race condition exists also for the daily debmonitor cron, but with a much smaller propability of hitting it.

Opening this task to find a clean solution.