This is probably related with some session problem. Please try to disable cache and select database as a storage for sessions (in global Joomla settings). You can also try to increase session time to avoid problems that your session ends when you are trying to send message.
This means that your mail settings are probably wrong or reCaptcha is wrongly configure. Please start from disabling reCaptcha and review your global mail configuration - please make all tests on regular contact form.