Interesting topic.
The thing is that appeal in team building essentially says that "The better team must always win", is a similar attitude in Poker where "The better hand always win". Of course, unlike Poker, there is much thought to be put into each team - and executing strategies.
I believe that luck is something gamefreak put into the game simply to increase the variety within the battle. Without luck, matches are essentially over the second the battle starts - much like in Chess where people know the "best moves" based on the situations and, without a luck factor, people put in a lot of thought into the moves and try to predict what the opponent to do. In this sense, the only "luck factor" in chess is your opponent - which isn't really "luck" at all.
EDIT: This statement is based on the assumption that both players are equally skilled - nearly all my statements I ever make assume both players are "experts" at the game.
Hence, we see that gamefreak wanted the game to be a more instinctive, much like the bullshit they advertise in the anime - this is done through luck, where the best planned strategy does not always win, and there is always this factor. Don't say people don't play by instinct - because many good players are unable to explain clearly why they think certain things are "uber" or not - there is a huge factor of "instinct" within the game.
Hence the removal of luck essentially limits choices within the battling appeal of the game.
There is an easy solution to all of this - to increase the appeal of "team buliding" and battling at the same time. Much like one round in Poker does not decide the game, make each match best out of 3, with counterpicking with "sideboards". This is an idea that was suggested multiple times in the past through one way or another. By having more matches, the "better team builder" wins overall, and not only that, but increases the appeal of team building by offering greater variety through sideboards. It also adds to a level of mindgames that the battlers will want, and critical hits suddenly matter less unless you are unlucky enough to get haxed a few times in a row. But then, it's "Pokemon".
Hence, I believe multiple matches, best out of 3 or 5 or whatever, is the best thing to do rather than modify game mechanics. We modify our playing format, not the game itself. That is how the metagame is, no? We modify the format we play the game to be the most competitive.
I like OD's idea of speedtie though
EDIT: Alternatively, we can create a god and claim that he dictates the realm of competitive Pokemon, and blame it whenever we get haxed. And we can write epic poetry about the rise and fall of great Pokemon players because of the fickle mother of chaos during the great War known as the Smogon Tour. We can also exalt our admins to the position of half god half man so they have absolute authority over everything without petty questioning from us mortals because they are INFALLIBLE