I have a lot of users who get that exact message, and can't post.

I've narrowed down the problem, and I even have the issue in my trouble-shooting section. Here's what I tell users:

Quote
When you try to post a new topic, or make a reply, you get the following message or similar:
"The host you are trying to send the input from is not a valid host."
This means you have changed something on your local PC that effects security settings. Most commonly this means that you have installed or modified settings in either the Norton or Zone Alarm firewalls, although it may also mean that your browser security settings are too aggressive.

To test, turn off any firewalls you may have running, and try posting again. If you can post successfully, then you will need to change the security settings of your firewall.

More often than not, it's either Norton or Zone Alarm, and as soon as users turn off those firewalls, they are able to post. Gizmo is right about the referrer checks - Norton and Zone Alarm are real funky about that.