It's possible that your IRCd can deny the use of nicks using wildcards. Some ircds like unrealircd support this ability. There is also an older modules called ns_wildforbid that's written by Trystan. Perhaps google can help you find it. There is also a cs_wildforbid for forbiding wildcarded channels somewhere on the net too.
Of all the options, making the ircd perform this ability is best.