Ok, I think I know what is causing it!
When I go to the contact form and send it, it works fine, but then when I hit the back button and type a different message to send, it doesn't work.
I think somehow when you hit the back button, the PHP script is not reloading, and therefore does not send it because it just executed the same command?
Going to the address bar and typing the address of the contact form, and then filling in the form, and pressing submit again, works.