After refreshing my memory here: http://en.wikipedia.org/wiki/Hostname ...which references (what appear to be) the relevant RFCs, I recall that underscores are definitely not legal, but the corner cases (and instances of blatant [cough]Microsoft[cough] disregard) are interesting...