sendmail is not delivering messages to recipients

sendmail is not delivering messages to recipients

I have run into a number of problems getting sendmail to work. None of the
solutions I've tried have worked.
First: sendmail was hanging for 60 seconds and then not sending the email.
To solve this, I used suggestions from the web to set my /etc/hostname to
a fully qualified domain name (FQDN) and then put that in /etc/hosts as
well. This did get rid of the hanging, but I still never receieve any
emails sent from sendmail.
Second: Installed postfix
This did not fix the issue. Sending an email via sendmail or mail at the
command line both fail. Example:
echo "a message" | sendmail someemail@gmail.com
echo "a message" | mail someemail@gmail.com
Both commands return instantly without error, but no email is ever
recieved at the gmail account.
I made sure a port was open at 25 in the router as well (although this
shouldn't be an issue as Thunderbird can send emails behind the router).
I need to get this working for PHP but cannot figure out where in the many
steps from the program to the remote email server it is failing. How would
I figure this out?