Personally, I'd like:
- No consecutive capitals (NAme = no)
- No more than two capitals per 'word' the entire name. ('JoHn SmiTh' is allowed)
- No more than two spaces or hyphens, and they can't be consecutive. ('Bob-the-awesome' is allowed)
- Each 'word' no longer than 12 characters, with a combined total of 20-ish. Each word no fewer than two characters, with a combined minimum of four.
- No underscores at all.
- No numbers at all.
- Only certain symbols are allowed, they can't be consecutive, and you can only have two symbols total.
- Accented characters are allowed, but no more than three total.
- Blacklist of names (common swears and etc...)
- Whitelist of good names that fit to the theme of the game auto-suggested to users (five randomly chosen names are displayed, but user can still enter a custom name).
I'm also a fan of separation of 'user name' and 'display name'.
If, as luke2006 mentions, players can also earn titles, they ought to be able to select from their unlocked titles, or choose to go without a title, to fit the theme of their name and roleplaying (or non-roleplaying).
For example, I'd allow names like "Gandalf the White". However, that user might not want, " the wise" appended as a earned title to his name, if that means it'd ugily display as "Gandalf the White the wise". If it was, "Gandalf the White" with under the name, "Wiseman", or "Master wizard", that'd be fine (but users should still get to choose whether it displays or not). In the same way, if a user is in more than one guild, he should get to choose what guild name he displays (or whether he wishes his entire guild alliances to remain hidden).