From the domains you mentioned as rejecting your emails, I'm about 99% sure that it's related to not using the right SMTP for your email sending.
Btw, also note that having the "From" setup to the user's name, as is the default setting in this Contact Form plugin, is actually illegal. This is because your sending server is your OWN website's domain, but the "From" header is the user's submission, which is likely another domain, such as Gmail.
This is exactly how spamming and phishing works.
The solution we have settled for is to have the From "NAME" to be the submitted name, but have the actual email address as our own. Because the SMTP server is our own. In other words, in Contact Form, the From is configured like this:
username <info@mydomain.com>
The From is NOT configured like this:
username <useremail>
This second case would be illegal, as the sender's domain will seem different from your mail server's domain name. Phishing, in other words.
We quickly got over the idea that the From should be exactly as if the person was sending the email to us. That is NOT the situation here, and I think the Contact Form plugin author should change the default. It will reduce about 30% of the questions being asked here :)