Well, I am on 2 day vacation from work and have pulled myself away from Battlefield 2142, FFIII, and Tales of the Abyss. This topic appears best to start with.
There already is a name change system in place, I quote from here:
http://www.guildwars.com/support/leg..._outcomes.php:
* For unacceptable character names, a mark will be placed against the account and the character will be blocked. This means that the character and all the inventory items and attainments associated with it will be inaccessible until the character has been renamed. The account will also receive a mark, and therefore will be inaccessible for whatever period of time is called for within the escalating suspension system.
Granted, this is for reported offensive names, but it would not take much effort to take this batch job, or whatever they call such processes at ANet, and integrate it into the store. They charge $5-10 per name, user buys a name change, app queries db to see if name is taken, prompts for another name if that one is taken, updates aka 'changes' just like it does for reported name violations, and ANet wins. They get $5-10, user feels satisfied that their name is changed.
Also, I do believe they lie at times, like all companies. The best way to get your client to get over what ever change the devs consider trivial and not worth doing, is to tell them it is not possible. If ANet has a system in place for when some one reports an offensive name, then it is possible to modify and integrate it into the online store. If it is not possible then ANet lied about the offensive name list. They have also proved they can integrate database changes with an online purchase into the system, via skill unlocks and character slots in relation to an account.
Forgot to mention:
As mentioned above, normalization is not good in the real world. If your db is fully normalized, you have to unnormalize it to use it, which creates overhead. Storage and memory are cheap now days.
This is speculation and educated guessing on my part, other than what I pulled from the guild wars conduct breaches. Like the auction house (unless this has been added since I started my GW break), this is something they probably do not want to deal with.