When you use WINS Manager to delete records, they are deleted from the display and queued for database deletion. If you stop and restarts the WINS service before the physical deletion occurs, WINS Manager will display these 'deleted' records.
When you delete records in WINS Manager, you must allow enough time for the queued deletions to be processed and to reach the replication partners. This could take 30 minutes or more. Do NOT stop or restart the WINS service until the queued changes have been processed.