For minor rule breaches by new users, don't send them a message telling them how to use the system. New users need help using the forum system, they do not need criticism. You want them to feel that you and your community is welcoming, friendly and helpful. You don't want them to feel you are pedantic and overly strict.
The wording of you message is important. On the first rule breach, just move the post to the correct section of the forum and don't say anything. Most users I see only post once or twice (though they may read the site for longer) so the likelihood of repeat offences is low anyway.
On the second breach, move the post again and send a message but word if extremely carefully. Don't mention rules, but rather make out that you are helping the user. For example, "You post has been moved to 'some section' as we believe it will be answered more effectively there. I hope you find this of assistance"
Only if the user was maliciously and repetitively breaking the rules would any message be sent about rules and such users are probably heading towards a block anyway so I wouldn't worry about losing them.
On a side note, you might want to think about restructuring your forum. A large number of categories doesn't really help the post to be answered. The same people read the all the forum. I don't believe that many people only view a section of a forum. This website for example doesn't really have sections at all. All the posts are in one stream and everyone here seems happy with that. Really the sections don't help answer questions but help people read the forum. But good tagging and a search system could replace that, as it does on Stack Exchange sites.