Old topic, but I wanted to post my resolution for anyone else who stumbles upon it.
-Launch WDM
-Expand “Update Manager” in the tree
-Select “real time commands”
-Delete all queued commands in the right hand pane
It seems that commands against stale device entries were the most common cause in our case. Until the queue is empty, new delete commands will not process.
Hope this helps!