I say go with a Namingway system.
You can change your name as many times as you like, but only in certain places, and probably for a fee, but regardless only via NPC. That way it doesn't look like such a hack, "setnick bill" is replaced with
NPC Code:
Enter your name:
A B C D E F G H a b c d e f g h
, etc. Or it would be if we had spiffy sign controls, but anyway. That'd be nice on NPCServ/P2P worlds anyway.