Perhaps just a personal message, similar to the 'You were mentioned in a thread' one that simply states

'Your post in XXX thread was removed for the following reason "xxxxxx"(whichever admin/helpdesk member could write a few words as to why it doesn't meet the forums requirements) Click here to view which post'

You could then be linked to a temporary link that displays which post was deleted, so you can maybe copy/paste it and amend what bits you think may have not been okay.

The admin/helpdesk member who deleted it would never be named, to stop them getting abuse for it, and the link where you can view the post could be automatically deleted after say, 24 hours, as to not take up too much space?