Ok there are several items that you have to consider.
Due to the high amount of hacking traffic and spam traffic most host servers have a firewall that blocks out going email.
What is you URL and is your email address from your website. For example if your website is http://mydomain.com and your email address is like email@example.com your email address is hosted on your server?
Many hosting services will block forms sending emails if your email is not registered in your mailbox or your mailbox is not activated. That means if your website is http://www.mydomain.com but you use an email like firstname.lastname@example.org they will block your email from going out.
To activate your mailbox server you only need to create an email address like email@example.com or any other address like firstname.lastname@example.org
You will need to ask your host tech support to disable the block for the outgoing email from the forms.
Another reason they block your email is if some of the fields in your email are not set to a valid email address. These are the "from":" and "reply-to" fields.
You will find that the only email address that never have problems are the ...@gmail.com but I have not checked yahoo email addresses. They will go out even if you do not have a mailbox server. So if you had tested with a gmail address it can be misleading.
Many email addresses are hosted by Google Apps. Which means that if your email address is email@example.com may not be hosted t http://www.mydomain.com but on Google Apps. In that case you will have to install a SMTP plugin in WP. Set SMTP host to smtp.gmail.com and port to 465. There are two other port addresses you could try if that does not work and they are 25 and ... sorry I can't remember the other port address. port 465 will normally always work.
When you install SMTP plugin ensure that 'ssl' is enabled ie secure connection prefix. and ensure 'authentication' is enabled otherwise Google will reject the email.
You could create an email in your mailbox as firstname.lastname@example.org but use a Google Apps hosted email like email@example.com to send out your messages.
I suspect that the WordPress mail function by itself cannot send emails to Google Apps hosted email address which means you will need to install SMTP plugin and your emails must be generated from a plugin and not WP itself.
One more thing, if you just created an new email address in your mailbox it may take a few hours for dns propagation. Which means you will not see any email being received for a few hours.
Let me know what you had done.