I'm using Fast Secure Contact Form by Mike Challis - no problems.
There are sever points you will have to consider.
1. Have you activated your mailbox on your host? Just creating a email address in your host will activate it. It may take a few hours for the dns to propagate so come back the next do to do your testing. If you do not have an email address registered in your mailbox some host will block all emails from going out.
2. Ensure all fields in the contact form are filled up eg 'from', 'reply to' ... as some hosts will not send the emails out if there are blank fields.
3. Ensure that your from email address is from your domain. For example if your domain name is mydoamin.com and you use an 'from' email address of another domain name like email@example.com chances are many hosts will block from going out (prevent spamming or hijacking).
4. Install an SMTP plugin. If you are sending emails to a Google Apps hosted email you will need to install an SMTP plugin with SMTP host set as smtp.gmail.com, port 465, Secure connection prefix set to ssl.
5. Some host firewall will block the emails from forms from going out. You need to request them to disable the block.
Check these out and let me know.