To me, the single biggest problem with evil campaigns and evil characters is that everyone has a different idea of what "evil" is, or what it should be. I've actually seen alot of evil PCs over the years.
I've played in a Forgotten Realms game that was supposed to be "evil," but it didn't feel substantially different to me. We still fought orcs and Red Wizards and all the typical FR type of enemies. We once fought a party of good adventurers devoted to Mystra, but even so, it still felt like a regular old game with different wording on the character sheets. I did have some conflict with the other players, I played a cleric of Gargauth and was told to pull back my immersion in evil. I did was engage in some drug/alcohol abuse and seduced young virgins and the like and it rubbed the players the wrong way. I also required some justification for using healing magic on them (as an evil cleric, he spontaneously cast inflict spells, so it was a pain to prepare them). My cleric kept a few heals for himself, but there was tension with the players because their characters had to actually convince me that it was worth something to me to heal them. I don't think that the whole "evil" thing really sank in with that group from a roleplaying perspective--I certainly wouldn't be begging a strange, black-robed, devil-worshipping priest to cast spells on me when I'm wounded.
In a Greyhawk game in early 3E, we had an evil monk in our party. He was a streetfighter and a very brutal, "that which does not kill me, makes me stronger" type of character. It worked for him. My character was a chaotic good wizard that focused on illusions and charm spells, so we were polar opposites. Being pragmatic, I gladly let him go interpose himself between me and the monsters. We sniped at each other alot, but it worked, since we both realized our utility to one another and kept it at that. I thought it was immensely cool--the tension between our characters was both reasonable and added to the game. Ironically, we developed a stronger camaraderie when a paladin came after us (him for being evil and me for being chaotic).
I did an evil campaign in my homebrew in 3E and it worked reasonably well. The evil druid ravaged travelers with animals and worked to corrupt the town's drinking water and spread disease. The sorcerer used illusions and charms to cause a paladin's husband to commit infidelity, he ended up committing suicide rather than let his paladin wife find out. The party actually banded together and raided a dungeon--not to kill everything there and loot it, but to take it over for themselves. The party became lords of a dungeon in the marsh instead of nobles in a shining kingdom. It was fun and the players handled it well.
It seems most successful in an Oriental Adventures type of campaign, where people care alot more if you are lawful than whether you are good. I saw a lawful evil samurai that was upheld as the epitome of honor--he was willing to do anything that his daimyo required of him, which was percieved as being totally selfless. Soldiers under his command might die, but the prevalent attitude was that it was to be expected for a soldier's life. His cruelty and sadism were commented on, but it was feared rather than reviled. His discipline and grim determination were indeed the stuff of legend, at least in our Kara-Tur.