Well, I like the idea and fully support it. I'm just going to state that first, before I get rant-y.
However, I think that there should be severe limits on this kind of thing. For example, perhaps everybody gets one "Slot" for a character like this, and additional "slots" can be earned through various means. Therefore, making it a unique gift. (Granted the application would still have to be amazing, etc.)
As for the kinds avaiable, I think that some "Minor" races should be accepted. For example, a good rule of thumb is "If it attacks you anywhere, or you have to kill it for a quest, it won't be accepted there!" For example, Broken Ones are accepted in the Alliance like any other Draeni, and Ogres are occasionally found in Horde towns.
As much as I hate to say it, I think that if someone wants to create a character that is "not so easily accepted" like a Murloc (which I would absolutely love the oppertunity to play), Kobold, Knoll, or something like that, they should be allowed, but given something as "Deterrent". For example, if a current character of yours were to see one, would they attack it on sight? (or avoid/run from it?) If so, then it probably won't be accepted in most areas, and therefore be a major target. Of course, there would of course be the occasional "Ambassador/Diplomat" who might be safe in some cities, but when most people see it, they usually think either: "EEEEK! Killitkillitkillit!" Or "EEEEK! Run Away!"
Basically, I think that this should be a privelage that can be taken away if a character is being unused, or poorly used. Just remember to keep an open mind about it. After all, I did expect goblins to eventually join the Horde, but Worgen joining the Alliance? I was completely (and pleasantly) surprised!
And if it doesn't work out? You can always just cancel the whole thing and pretend it never happened
