Today a new user posted a silly comment as an answer, I flagged it and Kortuk appropriately deleted it (it was too silly to convert to a comment, really). Does this guy get a notification of this? Otherwise I'm afraid he'll post similar things. And most users can't see the deleted answers, but I can, and that's not always a plus.
No, users are not notified of a delete. If a moderator places a comment on the question and then deletes it this will still appear in their inbox, otherwise they had no notice of this action. For science we verified with a moderator comment and ensured all operated as normal. With a moderator comment:
But this would not occur from a user such as stevenvh whom has high enough rep that he was performing moderation, just without the star. This is currently a discussion point on meta.SO, Show some support if you would like the feature also.