I don’t think it is a technical challenge, lol 
But with millions of players, do you really want to require unique names? Nothing is more frustrating than to get “Sorry! The name John is taken, can we interest you in John2734?” I think it is great that you can pick any name you want, even if it is taken. And I haven’t seen it to cause much problems either.
That said I would have made the alliance names unique. At least player X from alliance Y is most likely unique then.