This was such a massive nuisance when I ran forums. I would get reports from other members basically yelling at me to get rid of the idiots doing it. But unless it's a spam bot you still have to be fair.
On zetaboard Atrium we gave warnings to not do it again typically. When they did it again they were moved into a members (PM) group which mean this group had disabled PMs. I can see how that was embarassing in a way because it was obvious who did it or who didn't.
On current Atrium, there are no warnings - because typically if people did it once they'd do it again. PM rights are taken away immediately. I'd only return PM rights maybe 6 months down the road. You might say this is unfair, but to me, most people know it is against the rules and people try to make use of the system anyways.
It bothers members, bothers me especially when our rules specify where you can advertise (within your sig), and that's it.
I've never really had a problem with it on my forums. I think it is something that is generally done by new members who are hoping to swoop in and get some people to visit their site. Its generally not a good tactic and very in-effective. I think taking away PM permissions is the best course of action, but I do think giving a warning first isn't a bad idea.
There's a special place in hell for those who PM advertise....and they see the light pretty quickly on all the forums I used to manage. We usually just banned them right away. 😛 No mercy.