this had me perlexed for days. mail doesn't work, or give an error (unless I do it through my hosting company). Why? Because mail does not allow you to specify an smtp sever to relay your mail through, and unless you can go through the the grief of setting up you machine as a bonafide mail server, you're attempts will get rejected by the recepient as spam (without informing you).
use nail, which does allow you to specify an smtp server to relay your mail through. You don't need to go through any sendmail config files.
The problem with the standard 'mail' command is that it assumes that the machine it is running on is a full-fledged SMTP server. So unless you've configured your machine to be a bonafide mail server (or to act as an SMTP relay), then your mail will not go anywhere outside your machine (i.e. it will only work for addresses local to your machine, e.g. some_user@localhost). There is no way to specify an external SMTP server (like your ISP's) to use with the 'mail' command. That's why you're getting a dead letter.
If you want a command-line mailer that does support using an external SMTP server, then get nail from Fedora Extras. Nail supports specifying an external SMTP server. You can do this on a per-mail basis, like this: