This had me puzzled for a bit, but Nanoblogger, being the cool thing that it is allows you to use Bash commands directly in the blog template files, which means I could put:
href="http://www.haloscan.com/comments/i5m/`echo "$NB_EntryID" |sed -e 's/[^0-9eTtx]/_/g'`"
Which is just pretty cool. The bits between ` and ` get executed. I've not used sed before, but have used awk and regexp, etc, very briefly: the "s" stands for substitute, the [^0-9eTtx] matches any character that isn't a number, letter e, T, t or x. The underscore, "_" is what to replace the matches with and the "g" means replace all occurences.