In this case I’m talking about posts I myself deleted. I understand your use-case though, but couldn’t this still be achieved without showing the full post? Eg. only show a highlighted ruler of sorts.
Here’s a quick and dirty mockup of what I’m suggesting: http://files.naatan.com/kVl5/F5HAQnI1.
I’d probably show some more relevant information (first line of post, avatar?) but you get the idea.