A historical perspective:
Early editions of D&D were very rigid with respect to game concepts such as "race", "class" and "alignment". A magic-user couldn't wear armor because, well, because it wasn't allowed, that's why! An elaborate back-story developed that metal fouled up magic to "explain" this game mechanic, which required another backstory to explain how metal didn't foul up spells cast by a multi-class magic-user, which required another backstory ad infinitum.
As RPGs in general evolved, D&D (or D20, as you prefer) evolved along with it, to the point that the mechanics are much less rigid. It's less of "that's forbidden, and don't ask the man behind the curtain why", and more of, "Ok, you can do that, but there's a trade-off, and here's what it is..."
I feel that although the use of alignment as a game mechanic lags behind the development of some of the other aspects of the game, it nonetheless is moving in the same direction and for the same reason. Old editions had a prohibition against Paladins so much as adventuring with evil PCs for a single adventure, and even restricted them to adventuring with neutral characters "for a limited duration and only for a good cause". I suspect that came from Gary Gygax, who brought so much of his own views to the game that some of this practically became dogma.
As the other game mechanics evolve, so should our outlook on alignment. What is the purpose of a paladin? Why is a paladin special? Why do paladins have powers that other classes don't have? Well, all classes have abilities that other classes don't have, so maybe paladins aren't so "special" after all. In earlier editions of the game, there was a distinct advantage to some character classes. In 3.5, no class really has an advantage over any other, save for a particular (perhaps preferred) style of game play. So, since a 3.5 paladin has much less of an advantage over a 3.5 fighter than does a 1.0 paladin over a 1.0 fighter, there is less need to balance the classes by restricting the paladin class in 3.5. That doesn't mean that alignment is meaningless to a 3.5 paladin, just that it need not be so rigidly interpreted as to provide a "balancing" disadvantage.
A paladin is an agent of his or her deity, charged with representing and championing law and goodness on the prime material plane. That's enough, right there! Could a paladin accompany an evil PC (known to the paladin to be evil) on an adventure? Well, what's the purpose of the adventure, and what's the likely outcome? If the whole motivation is for the paladin to "get phat lewt", then it seems a perversion of the game mechanic. If the purpose is for the paladin to attempt to change the alignment of the evil character, not only should it not be forbidden, co-adventuring should be encouraged! Finally, it may be necessary for the paladin to accept the services of an evil character in order to accomplish some greater good. Does this "taint" the paladin to an unacceptable level? Which is better, to scrupulously avoid all evil, or to do the most good that is possible? This sort of moral dillemma is perfect for the game, and can make for very good role play. Ultimately, the narrative should be king...is the story of the adventure worth telling?
I've been pondering writing up an evil character for LEW, one that is truly vile. That's a long-range activity, since I'm fine with one character right now and would probably bring in a non-evil psionic character if I felt obliged to start a second one. But I usually play goody-two-shoes type characters, and thought it worthwhile to consider a walk on the dark side as a useful adjunct to the LEW narrative. I got to thinking about how a truly evil PC would fit into this game, and took into consideration some of the previous discussions on +ECL races, having "traveling papers" to get into cities, etc. I concluded that it was viable, since all the traditional earmarks of evil PC's would be an anathema to an evil character in LEW...and I'm talking about PvP, intra-party theft, that sort of thing. Do that, and even if your character doesn't wind up in the city jail, he'll spend an awful lot of time at the Inn trying to find both an employer and a party who will have him.
No, in LEW, an evil character has to be more subtle. Going on adventures with good types suits him just fine...but while they're motivated by saving the princess or enhancing their reputation, he'll be motivated by sheer greed or political ambition. He won't backstab a party member, but an elaborate political betrayal that takes several adventures to arrange will be right up his alley. He won't pick pocket other PCs or steal from their packs, but he'll be all too happy to report that there was nothing of interest in the alcove of the ruined monestary while secretly slipping the remains of the gold candelabra into the folds of his cloak. Against that background, why shouldn't there be a way for good and evil PCs to associate? In RL, people are forced to associate and deal with others who they consider untrustworthy, unreliable, or unsavory every day. Why must LEW be any different?