Just a FYI, recently we converted our networks over to the corporate network. This changed our DNS server's also. Unfortunately, nobody cares about linux or unix in these Microsoft worlds of Microsoft exchange, so nodody cares about our DNS still pointing to an non-existant mail server.
In other words, a fresh out of the box linux server with no configuration at all, just install sendmail, and the mail command would work. That is, of course, if your DNS server knows what to do with email. Ours no longer does, so I have to configure sendmail with an MX record and point it to a valid smtp capable server.
I'm telling you this, in case you have sendmail installed and the mail rpm, but still it's not working.