I had a bit of trouble setting up the wp-contact-form plugin for my wordpress blog that was hosted by freehostia. At first I was using the free package, so I couldn't send out any mail. I solved that by saving all messages to a directory, and password protecting it.
When I updated to a payed package, I still couldn't send out any mail. It turned out that the From header had to be an existing email that I had registered with my freehostia account, and wp-contact-form used "From: <email@example.com>" I solved that by modifying the plugin, changing From to the administrator's email set in wp options, and putting the person's email as a Reply-To header.
If anyone is interested in these modifications, check out my post here:
http://www.krizka.net/2007/09/02/wp-con ... -tracking/
I added a few more features, like user tracking too. Check it out!