If you go back through your WF and look at the Delete permissions, could it be that the file passed through a State where you (or more specifically the Group(s) you're a member of) didn't have the Delete permission?
IIRC, Delete is affected by what is called a "negative permission" (or something like that), where once you lose the permission, you will not gain it back even when successive WF States grant that permission.
Unfortunately, we've run in to that scenario here quite a bit...when we first built the WF, the user community predicted that once a file reached a certain State (say, approval of some sort) they would never want anyone to be able to Move or Delete it. Now 3+ years later, they can come up with 20+ reasons why they want to move *this* file or *that* file. And every time, they have to get the admin involved....not difficult, just annoying for everyone involved. So we've added those Move/Delete permissions in for a select few, and it works as advertised on any new files going through that part of the WF...but old files are tripped over on a regular basis, much to the users' dismay.
Thank you for that reminder. The initial state these files pass through does not allow delete permissions. This, as we know will prevent us from deleting files unless we check "Ignore permissions in previous state"
I have checked this box and the issue is now fixed.