Hmmm. I'm not aware of captcha on the private messages page - should only be on the registration page.
Perhaps it's ad admin vs user thing, but I've never seen it. Perhaps a few more details?
I will note, I know of a problem (see the thread right below this one) that I'll try to take care of tonight. That may help things.