Have you checked that wp_mail() is working if you provide all the arguments is needs?
Try creating a simple template file in your theme folder, like so:
<?php
/* Template Name: Test */
get_header();
// $headers = 'From: My Name <myname@mydomain.com>' . "\r\n\\";
wp_mail('myname@mydomain.com', 'The subject', 'The message', $headers);
get_footer(); ?>
Then create a test page using "Test" as the template. Preview the page (you shouldn't see anything on the page, actually) and then check your email. If you still get nothing, uncomment the line with $headers (just delete the two // at the start of the line). Save the template, reload the test page, and check your mail again. If it now works, the problem is that there is no "from" address being set when wp_mail is being called elsewhere.
On my host, simply creating an email user "wordpress@mydomain.com" fixed the problem.