If you are getting the dreaded “There was an error trying to send your message. Please try again later,” and you’ve tried the Captcha fixes, then there’s another thing you should check.
Contact Form 7 could be using WordPress’ function to block comments to block the submission of your form.
Go to Settings > Discussion > Comment Moderation. If there’s an IP address in this box, it could be blocking your form submission.
Note: If you are using Cloudflare, it could be blocking any that seem to be submitted from the server IP. You need to fix that – but removing your server’s local IP from this box will allow your forms to be submitted again.