|There's more than one way to do things|
Regarding your css example, I did a quick test with two recent builds of Mozilla (Build 2002091208/WinNT, 2002100104/Linux). A <div class="test_underscore"> was perfectly stylable through css.
Looking some more at the Perlmonks code, I noticed that both th.nodelet_head and tr.nodelet_head are used. Specifying a generic class ".nodelet_head" doesn't work, as it is less specific than the original style specificatuions. Playing with Mozilla's DOM inspector is very helpful to debug CSS issues like this.
My solution is simple (for Mozilla at least): add the "!important" qualifier to your styles, this will override more specific but "unimportant" styles.
This Works For MeTM.
On a side note, there is no mention of "css" connected with "underscore" to be found in Bugzilla - so I don't think this is a bug, at least not with current builds.
Update: Fixed a typo ;-(
Update 2: Apparently, from the CSS level 2 syntax specification I seem to conclude that the underscore in style identifiers indeed is illegal. Still, this works just fine for IE 5.x+ and Netscape 6+ (Mozilla) in production code on the site I'm maintaining as well. Hmm, maybe I should fix that one day...