When sending emails through sendmail - whether it's a standalone server, or a relay server, the system sometimes wont expose itself to the outside world as being from a valid FQDN. Actually, the default for sendmail is to expose itself based upon best guess, which typically is by hostname. Because hostnames are essential to our environment (the ood.ops name) - I strongly suggest against changing the systems hostname to fix this problem. Because of this, sendmail servers will expose themselves to the outside world as <hostname>.ood.ops. I've seen twice now where this has also led to email servers as being identified as spam sources because the 'helo' isn't a valid FQDN. Please follow these steps to test this.

1. send yourself an email from the server itself. Make sure the 'mailx' rpm is installed (for hybrid customers, this is not installed by default on cloud servers)
rpm -qa | grep mailx
sudo yum install mailx

# mail <username>@Latheef.net
Subject: <type in whatever here>
<this is the data field, type whatever you please>
<enter a '.' (period or dot) then <enter> to end the email>
CC: <hit enter - no need to CC anyone>

When you receive the email in gmail, you need to view all of the headers. To get the headers you will need to:

1. open the email
2. in the drop down next to the 'reply' box, select that and 'show original'

Once you see the headers, you want to look at the last 'Received:' line before it hits the google mailservers. Keep in mind, your 'Source' is the bottom most 'Received' line, and your destination is the top most 'Received:' line. So you would read the headers from the bottom up, and not top down. An example would be:
Received-SPF: softfail (google.com: domain of transitioning gwright@jobvite.com does not designate 65.200.35.206 as permitted sender) client-ip=65.200.35.206;
Authentication-Results: mx.google.com; spf=softfail (google.com: domain of transitioning gwright@jobvite.com does not designate 65.200.35.206 as permitted sender) smtp.mail=gwright@jobvite.com
Received: from localhost.localdomain ([65.200.35.206]) (using TLSv1) by na3sys009amx188.postini.com ([74.125.148.10]) with SMTP;
    Thu, 08 Sep 2011 21:55:02 GMT
Received: from localhost.localdomain (localhost [127.0.0.1])
    by localhost.localdomain (8.14.4/8.14.4) with ESMTP id p88Lt04i001960
    for <gwright@Latheef.net>; Thu, 8 Sep 2011 14:55:00 -0700
Received: (from gwright@localhost)
    by localhost.localdomain (8.14.4/8.14.4/Submit) id p88Lt0PZ001959
    for gwright@Latheef.net; Thu, 8 Sep 2011 14:55:00 -0700

The important line here is:

Received: from localhost.localdomain (65.200.35.206)

As you can see from this, currently my desktop VM is 'helo'ing to the world, or exposing itself as 'localhost.localdomain'. This doesn't match my current hostname on my VM, but that doesn't matter. I assume it's getting localhost.localdomain from my /etc/hosts file. Without modifying the /etc/hosts file, or my servers hostname, there is a way to fix this in sendmail. In sendmail, you just need to open the sendmail.mc file and add the following macro line:
define(`confDOMAIN_NAME', `relay.host.com')

You will then need to rebuild the config and restart sendmail:
sudo make -C /etc/mail
sudo /sbin/service sendmail restart

You will then need to follow the above procedures to send yourself another test message and once again inspect your headers. You should see successful results like the following:
Received-SPF: softfail (google.com: domain of transitioning gwright@jobvite.com does not designate 65.200.35.206 as permitted sender) client-ip=65.200.35.206;
Authentication-Results: mx.google.com; spf=softfail (google.com: domain of transitioning gwright@jobvite.com does not designate 65.200.35.206 as permitted sender) smtp.mail=gwright@jobvite.com
Received: from relay.host.com ([65.200.35.206]) (using TLSv1) by na3sys009amx241.postini.com ([74.125.148.10]) with SMTP;
    Thu, 08 Sep 2011 21:57:38 GMT
Received: from localhost.localdomain (localhost [127.0.0.1])
    by relay.host.com (8.14.4/8.14.4) with ESMTP id p88LvaRv002029
    for <gwright@Latheef.net>; Thu, 8 Sep 2011 14:57:36 -0700
Received: (from gwright@localhost)
    by localhost.localdomain (8.14.4/8.14.4/Submit) id p88LvaBJ002028
    for gwright@Latheef.net; Thu, 8 Sep 2011 14:57:36 -0700

From the above, the important line is again, the one right before the google/gmail 'Received:' line.

Received: from relay.host.com (65.200.35.206)

Congrats. Now you've successfully told sendmail "I know you don't know what my public hostname is, so please use this provided one instead of guessing something that's incorrect for my purpose."