I tried to delete a post for a second time but was met with the following dialog:
This post has been deleted; deleted posts can't be voted on.
Why on earth does it say "voted"?
A delete action counts as a vote. In fact, most actions on the site count as votes. See here for a complete list.
So, trying to delete would be casting a vote, which you can't do since it is deleted.