As far as I know, if any file in the vault has been through a
state, that state can't be deleted.
I had this situation during implementation when we were developing
workflows. We had test files still in the vault that had been
through obsolete states, so the states couldn't be removed. As of
last week, all those test files were no longer in the vault, so I
was able to delete those states.