[Plugin: BigContact Contact Page] Said my message was sent, but it wasn't

This could have many reasons. However, the most common issue is that you host your email on a different server than your sites hosting. For example, using Google Apps for email. What happens is that your server tries to handle sending the email internally because the domain are the same (example.com and user@example.com.) However, the message should be sent to Google’s servers to be routed correctly.

The “message was sent” means that the server successful added the message to the outgoing queue. Here is the documentation page for wp_mail function. Note under Return it states

A true return value does not automatically mean that the user received the email successfully. It just only means that the method used was able to process the request without any errors.

The best solution would be to contact your hosting provider or search their forums.