Just posting this response as I ran into a similar problem with a workflow not triggering on ItemDeleted actions. The workflow I was testing was a simple notification workflow that got sent on add, delete, and updates. The email event used the list item to populate the body of the email, subject, etc. Add and Update events triggered the workflow, and subsequent email notification successfully. However, ItemDeleted actions were not working properly. The workflow was triggering, but the mail event was erroring out. 

My theory: I had a look at the k2 workspace and confirmed that the workflow kicked off successfully. It looks like K2 attempted to read the contents of the list item to use its values in the mail event. As the item was deleted, k2 was unable to read the item as it did not exist. I tested this by having a generic email not referincing any of the list item values, and this worked. 

Takeaway: for me is that when using an ItemDeleted event, you cannot use any of the list item values as the item does not exist so far as k2/sharepiont is concerned. Someone from K2 can confirm, but the ItemDeleted event should only be invoked if you plan on conducting actions that do not attempt to read the deleted sharepoint list item. I hope this helps!