One should be clear about definitions. As used here:
The hostname is subject to the restrictions of RFC 952 and the slight relaxation of RFC 1123
RFC 2181 makes clear that there is a difference between a domain name and a hostname:
...[the fact that] any binary label can have an MX record does not imply that any binary name can be used as the host part of an e-mail address...
So underscores in hostnames are a no-no, underscores in domain names are a-ok.
In practice, one may well see hostnames with underscores. As the Robustness Principle says: "Be conservative in what you send, liberal in what you accept".
In the 21st century, it turns out that hostnames as well as domain names may be internationalized! This means resorting to encodings in case of labels that contain characters that are outside the allowed set.
In particular, it allows one to encode the _
in hostnames (Update 2017-07: This is doubtful, see comments. The _
still cannot be used in hostnames. Indeed, it cannot even be used in internationalized labels.)
The first RFC for internationalization was RFC 3490 of March 2003, "Internationalizing Domain Names in Applications (IDNA)". Today, we have:
You may also want to check the Wikipedia Entry
RFC 5890 introduces the term LDH (Letter-Digit-Hypen) label for labels used in hostnames and says:
This is the classical label form used, albeit with some additional restrictions, in hostnames (RFC 952). Its syntax is identical to that described as the "preferred name syntax" in Section 3.5 of RFC 1034 as modified by RFC 1123. Briefly, it is a string consisting of ASCII letters, digits, and the hyphen with the further restriction that the hyphen cannot appear at the beginning or end of the string. Like all DNS labels, its total length must not exceed 63 octets.
Going back to simpler times, this Internet draft is an early proposal for hostname internationalization. Hostnames with international characters may be encoded using, for example, 'RACE' encoding.
The author of the 'RACE encoding' proposal notes:
According to RFC 1035, host parts must be case-insensitive, start and end with a letter or digit, and contain only letters, digits, and the hyphen character ("-"). This, of course, excludes any internationalized characters, as well as many other characters in the ASCII character repertoire. Further, domain name parts must be 63 octets or shorter in length.... All post-converted name parts that contain internationalized characters begin with the string "bq--". (...) The string "bq--" was chosen because it is extremely unlikely to exist in host parts before this specification was produced.