When i send emails to a gmail address, gmail shows a Question mark, with a message "Google could not verfy that mydomain.com has sent this message".

This looks pretty bad. How can we fix this?

Thanks