They have never worked if you _ever_ add permissions other than setting the context_id to some value. Also if a package creates groups or anything like that, forget it.
Andrew, I also was surprised. You would think that if you have a group.create, that group.delete would exactly reverse that. But somehow the whole delete thing didn't work out.
Recently I needed a package with data. And I needed to reload it from time to time. I used groups, new relationship types, relational segments. I had to create a whole set of delete functions to loop over stuff not deleted, just to get rid of all the junk.
Of course, not having a delete that works means that testing the package create scripts is hit and miss, something you don't ever want. I think there has been some recent work on fixing this.