Gmail say "This message may not have been sent by" and mark it as spam

When you have the form send to a gmail account, make sure you also

Set the “Custom E-mail From:” setting to a real email address on the same web domain as your web site.

That is what my form does and I get gmail email just fine

Let me know if you have success or not

Hi Mike, I tried by setting it. I also tried with and without the ” Enable when web host requires “Mail From” strictly tied to domain email account. ” options.. In both those cases, I will get the email fine. But the reply to address is set to my own account. So If I just reply in a hurry without checking, it will come to my account again ??

Never use the setting “Enable when web host requires “Mail From” strictly tied to domain email account.” unless you have to to even send mail.

Maybe another plugin is conflicting.
Look on the Admin – Plugins – menu.
Temporarily Disable (not uninstall) all your other plugins.
Does it work now? If yes, Activate the plugins one by one to determine which one conflicts.

The theme you are using could be causing it…
Do this as a test:
In Admin, click on Appearance, Themes.
Temporarily activate your theme to a WP default one…
“WordPress Default” theme(default for WP 2.0+), or
“Twenty Ten” (default for WP 3.0+), or
“Twenty Eleven” (default for WP 3.2+) or
“Twenty Twelve” (default for WP 3.5+)

It does not cause any harm to your WP to temporarily change the theme test and then and change back.
Does it work properly with a default WP theme?
If it does then the theme you are using is the cause.