I had the same issues. It turned out to be a problem with the cache.
I use the plugin WP Fastest Cache and the solution to the Contact Form 7 problem was to go into the settings of WP Fastest Cache and exclude the page (URL) with the contact form from caching.
This information set me on the right path:
https://peakplex.com/blog/check-contact-form/
