ITMS 8.1, 8.0, 7.6 with Deployment Solution configured
Cause
The recently deleted computer is still regarded as a managed computer
Resolution
In the NS console under Settings | Deployment | NBS General Settings Scroll down to the Redeployment (Managed Computer) Menu and tick the 'Respond to managed computers' option.