We use exim mail server, and I believe the settings are configured to our web-host's defaults. Where would go to view or configure these rules?

Seems like I was on the wrong track. Exim should do the job.

Some people do SMTP on their own, without using a mailserver that fully implements the RFCs.

Read http://news.ycombinator.com/item?id=1151123 to get some more insight about greylisting.

Check out your exim logfile to get more knowledge about your problem. In case you have trouble interpreting the data, just post an anonymised excerpt. I am sure somebody will help.

Thanks for the tip seven. ;)