Yes.

[Jonathan de Boyne Pollard]

H> In the SOA, they have "localhost." as the primary server,

... which is, of course, perfectly legitimate.

<URL:http://homepages.tesco.net./~J.deBoynePollard/FGA/dns-soa-field-semantics.html#DynamicDNS>

H> but there's no A record for localhost,

"localhost." is usually dealt with as a special case in everyone's proxy 
DNS servers.  See RFC 1912 for how it's usually done by people using 
BIND, for example.

H> halurban.com. 86400 SOA localhost. hostmaster.earthlink.net. ( [...] )
                                     ~
H> it's not in a fully qualified domain name.

Rubbish.  It clearly is.

<URL:http://menandmice.com./online_docs_and_faq/glossary/fqdn.htm>

H> What problems could this cause?

A greater number of calls to Earthlink technical support from people who 
don't understand DNS.

H> At times we are not getting all of our emails, it's very sporatic,
H> and it may only be like 5-8 emails in a day, but still would like
H> this to be fixed.

There go the chocolate-covered bananas again.

<URL:http://perl.plover.com./Questions3.html>

Find out what your mail transport problem *really* is, and fix that, 
instead.