I like all the ideas presented here: a short educational message now and then, a minimum of words for fist messages, and a folder for first messages like the IG model.
I also like the feedback idea, wheter it is similar to the one trustroots have, or just an allow/delete/block option. I think if you have too many first messsages being deleted/blocked maybe you could recive a polite informative message about the way to approach people on the community, and that this will be reflected on your community standing. Its educational and simple. And makes clear for the rest of the community this person is not behaving according to the correct spirit.