localhost prefixing problem

[Jude DaShiell <jdashiel@shellworld.net>]

I tried using exim4 and alpine to send a piece of email from one account 
to another.  I suppose I ought to have given this machine the same domain 
name as verizon.net rather than left it at localhost since even with 
address header rewriting localhost is being prefixed to the proper verizon 
header and verizon as well as the rest of the internet is quite correctly 
refusing this incorrect address.  Do other more reasonable possibilities 
for clearing this problem exist?