How can I force sendmail to use SMTP instead of internal relay?

I have a web server that was blacklisted from sending email because it was responding to SMTP HELO with localhost.localdomain instead of the domain name of my server (we'll call it example.com). I was able to get the server to respond to the HELO with example.com by removing localhost.localdomain from my /etc/hosts file. However, now any time I try to send email to an address with the same domain name, sendmail is attempting to deliver the message locally instead of sending it via SMTP to our actual mail server (which is hosted at Rackspace).

I followed the advice here: Why sendmail is accepting mails for hostname not present in local-host-names file? and ran

echo '$=w' | sendmail -bt

And got:

[mail]
[162.243.XX.XXX]
mail
[mail.example.com]
mail.example.com
localhost
[127.0.0.1]
example.com

From what I understand, sendmail considers all of those domains local. I set DontProbeInterfaces=True in my sendmail.cf file. Now when I run

sendmail -bt
$=w

I get:

localhost
[127.0.0.1]
example.com

I also tried removing example.com from /etc/mail/local-host-names, but sendmail still thinks that example.com is local. How can I get sendmail to stop attempting local mail delivery for example.com email addresses?

EDIT:

echo '$j' | sendmail -bt

produces

example.com

EDIT:

I tried changing the hostname from example.com to example, but now my SMTP HELO response is localhost and it takes several minutes to send an email. According to this: https://www.digitalocean.com/community/questions/sendmail-is-slow-to-send-mail sendmail expects hostname to be the FQDN, but I'm being told that it should never be the FQDN. Which is it?

This is in my mail.log:

Jul 28 16:40:01 localhost sm-msp-queue[1679]: My unqualified host name (localhost) unknown; sleeping for retry
Jul 28 16:41:01 localhost sm-msp-queue[1679]: unable to qualify my own domain name (localhost) -- using short name

Fix your server's hostname. No server should ever have a hostname equal to the naked domain name; this is but one of the many problems which occurs when you do this.

In your case Sendmail adds auto-configured "this host (email) name" ($j) to list of local email domains ($=w). Sendmail uses name reported by hostname --fqdn.

Recomended fixes:
Do not use "named domain" as hostname (as suggested in Michael reply)
OR
Change name used by sendmail as "this host mail name"