CNAME, MX , FROM address unable to deliver to verizon.net addresses

[ksmalley]

We have a mailserver named: entwhistle.jci.tju.edu
We have a cname "mail.jci.tju.edu" set up to point to entwhistle.
Recently we have been unable to send mail to certain domains, like
verizon.net.

We can telnet to relay.verizon.net on port 25

and the following works:

mail from: username at jci.tju.edu
mail from: username at mail.tju.edu  (tju.edu is a domain with MX records
as well)
mail from: username at entwhistle.jci.tju.edu

the following does not work:

mail from: username at mail.jci.tju.edu   (CNAME pointing to host)
mail from: username at mailbox.jci.tju.edu (no entry -- hoping it would
do an MX lookup on jci.tju.edu)

dig jci.tju.edu MX 
returns an MX entry which points to entwhistle.

How we can keep the mail.jci.tju.edu as reply-to address and still be
able to send mail to everyone including verizon.net addresses.

If we rename entwehistle to mail.jci.tju.edu with a true A record this
would probably work, but what would we do when we want to replace that
machine. Would we have to give that machine the same name and IP
address?  The point of the CNAME was to make this sort of switch
easier. Is this possible or not?

Thanks in advance.