Some of them are easier than others. I mean, it's easier to come up with a way to make combinations that already exist as NPCs and make them playable than it is to introduce novel combinations. For instance, Blizzard needed this whole little quest just to give us some exposition for Holy Cows back during Wrath, but they didn't need to "introduce" night elf mages so much as rationalize why they are associating with the night elves in Darnassus.
I don't think there's any combination that just flat out can't work. The hardest sells, IMO, are Dranei and/or Night Elf Warlocks. Just so much baggage there, it goes to the most defining events in both societies' histories.