What's in a hostname?

The common definition of a 'valid hostname' is often reduced to a simple regular expression, but as the saying goes: 'Now you have two problems.' Because hostnames are DNS labels and those... well, it's the DNS. All bets are off.