If they can PM then surely they can post???
I find either quoting from or pointing to the FAQ section usually works, and if they still can't suss it out after that then I tell them to power off the PC and go and do something else!
Or, are you saying that they are getting 'post not sent from a valid host' message? If so then they need to add your site to their firewall.