RFC 2181 liberalized the acceptable characters in DNS names back in 1997. But people still seem to be skittish about using underscore in hostnames. (For example, GoDaddy won't sell a second level domain with an underscore, like "this_bites.com")
In a few minutes of testing, a third-level hostname containing underscores "just works" on everything in my office. (e.g., that_guy.example.com, my DNS host is Amazon Route 53)
It "just works" on Win XP and Win 7, Mac OSX 10.7, IE8 and 9, modern Firefox, Safari, and Chrome.
Where could I expect it to not work?
(Why do I care? I'm assigning virtual machines to students, and I want to use the user ID they've chosen in the hostname to remind them that their actions on box are directly attributable to them. Unfortunately, a large percentage of pre-existing student user IDs contain underscores.)
To be perfectly clear, underscores have always been allowed in DNS since the very beginning. RFC 1034 has this to say about the syntax of labels:
That means: if you put hostnames in the DNS, restrict yourself to the rules for host names. If you put mail domains, restrict yourself to the rules of RFC 822 If you put DKIM or ENUM records in the DNS (which are not hostnames), restrict yourself to the syntax of those protocols. If you put something else, follow the appropriate syntax. But DNS itself will not constrain you.
RFC 1034 goes on to make a conservation suggestion on syntax which specifies labels without underscores. But this is only a suggestion. It says "The following syntax will result in fewer problems".
So for sure GoDaddy is wrong to deny you "this_bites.com". Even if underscores were categorically disallowed in host names, you might want to fill this domain with DNS names that represent something other than host names. DNS registrars and nameservice providers shouldn't disallow that!
The next question is, are underscores allowed in actual host names?
RFC 1034 says about host names that "the old rules for HOSTS.TXT should be followed". But if the rules for HOSTS.TXT were old when RFC 1034 was written, they're ancient history now! RFC 1034 was written as a time when usernames commonly couldn't exceed 8 characters and everything was ASCII. The world has changed.
I would say that there is no single set of rules that define what is a valid host name. It just depends on what the software in use supports as characters that may be part of hostnames it uses for systems to designate themselves and peers. By "software" I mean all of the pieces of software that deal with hostnames in one way or another, from the operating system through network monitoring agents and everything in between.
If you are reasonably sure that there is nothing in your environment that would choke on a hostname that contained an underscore (and I think that, these days, that's a pretty good assumption), then I think you're safe to use them.
If there is something stopping you from using underscores in host names, though, it's not DNS, and never was.
Android and Java seem to have issues with underscores in Domains. In particular the URI class in Java will fail to parse a URI properly, and throw UnknownHostExceptions.
RFC2181 merely clarified the same rules that were in place all along (it was never DNS itself that disallowed underscore).
The limiting factor regarding hostnames specifically is the definition of an Internet hostname and this is not changed by RFC2181.
For compatibility I think it only makes sense to recommend following Internet hostname rules for hostnames (essentially the recommendation that is in the DNS specification), while other kinds of names will have different rules.
As for whether a registry or individual registrar should impose Internet hostname rules on domain names is debatable.
The vast majority of registrants are going to use their domain names for hostnames and in that regard such a rule does make some degree of sense but from a DNS purist perspective there is no reason to have such a rule.