To my knowledge, underscores are not legal at all.  I sent Paul directly
a message I wrote for someone earlier this month who was arguing this
point with me, which outlined the sections of the specific RFCs which
apply to this situation.  I also attached this message, which I received
shortly thereafter, that I feel pretty much puts a nail in the whole thing.
 
On Mon, 22 Apr 1996 14:03:56 -0700 Lefty said:
>As much as I respect Marshall (I inherited his chair when I went to work at
>the Wollongong Group), if he says that underscores are legal in a host or
>domain name, I believe he's in error.  Underscores have been widely
>_tolerated_, but they are not, to the best of my knowledge, legal.
 
------------------------------------------------------------------------
 
The next minor release of BIND nameserver will be enforcing
RFC952 (as modified by RFC1123) hostname conformance as part of
its SECURITY measures.  Following its release hostnames that
fail to conform to these rules will be unreachable from sites
running these servers.
 
Hostnames (A records) are restricted to the following characters only.
 
    "A" - "Z", "a" - "z", "0" - "9", "." and "-"
 
The following characters are specifically excluded "_" and "/".
 
We are letting you know in advance so as to minimise the
problems this will cause.
 
If the specified zone has any records that don't meet the above
criteria, then any attempts for resolution of the name will
fail.  If your zone is pristine, then consider this a heads
up notice when other zones start failing to resolve names.
 
For a full description of what is allowed in a hostname please
read RFC952 and RFC1123.
 
RFC952: DOD INTERNET HOST TABLE SPECIFICATION, October 1985
RFC1123: Requirements for Internet Hosts -- Application and
                Support, October 1989