Though you state that PHP mail is tested and working outside of Joomla!, my suggestion would be to use the SMTP method. You can use the SMTP info of any email account you have that accepts SMTP connections (most all do). If you receive the message with the SMTP method, then you know it is a PHP mail issue.
If you still don't receive the message, then it very well could be an issue with the template you are using doing an override of the com_contact component. As such, other components/plugins/modules could be causing scripting conflicts, preventing the message from being sent.
To check to ensure the message is reaching the server for sending, check the "Mail Delivery Reports" on your server to ensure that Joomla! is actually getting the message through to EXIM.
Note: Many servers (especially shared servers) block the PHP mail function, so it could be the case that your host does that in the future without warning to prevent abuse. SMTP relays are fairly cheap (Mandrill used to be free!). If mail is a mission-critical part of your site, invest in a good SMTP relay service that can monitor every message sent and give you analytics for review.