The goal should be to combat spammers at registration, not somewhere else down the line. I know you can't catch every single one, but adding a second or even third spam-prevention measure to the registration process would be much more acceptable than requiring captcha to send PMs.
Everybody only registers once. Some people send several PMs per day. You tell me which you'd want to be more hassle-free.