The problem is that wp uses wp_mail, which almost never works on nowadays hostings. Sigh, sadly but true.
What I did, is just modded the wp_mail, replacing with simple
mail() function, and that worked like a charm.
Also you should make sure that the field from comes from your site's domain, otherwise 99% of hosting provides will block it right away.
Additionally you want to check your headers, and tune them accordingly to your server, so that it accepts your mail.
In my experience, I found support for my web-hosting useful for resolving this issue with emails.
Hope that helps... cheers.