Definitely a Rohan limitation to not have a Name Change NPC + ticket system (though it does give me ideas for developing one). I personally don't have an issue with the cost. As you say it should be high enough that it isn't abused, but accessible enough that you can actually use it quickly.
The servers don't need to be restarted for name changes. Your account does however need to logged off, then back on after though. It is the log in process that fetches your stable of characters (along with names) from the game data storage.