The DM's are very firm on associating with evil being a break of the paladin's code. You are not going to convince us otherwise. All of us have been involved on debates on the topic for years, and we are in agreement about it. It should be very clear. If you want to play a paladin and stay a paladin, you won't go questing with evil. If you are going to play a paladin, you just need to accept that, and work with it. Otherwise play a LG fighter.
1) Redemption - Redemption is often used as an excuse to travel with evil. When we hand out chaotic points, we watch first. If you are actively redeeming evil, we see that. If you are only using redemption as an excuse to go questing, we see that too. I can tell you that two of the DM's have played through this scenario before as players. On was an evil character on the path to redemption, and one was a paladin trying to redeem him. Here is how we made it clear that this was serious, and not just an excuse to quest.
A) An applicatoin was sent in for the evil character, asking the DM's to watch for good acts and such as they were working on redemption.
B) Hours and hours of NON-QUEST discussions and RP on topics like morality, the nature of good and evil, why the character was evil in the first place, steps to improve themselves, etc. This is a key component. If all we see is questing together, that is not trying to redeem them, that is helping evil get xp and gold, so that you can get some too.
C) Others were involved as well. Although one paladin was the key figure in the redemption, a number of others were also involved in discussions, to get more points of view to the evil character.
D) The paladin was willing to just eat the evil points along the way. He was willing to risk tainting himslef to redeem a soul. It's the risk you take. The paladin is likely to take alignment hits along the way. It's just something to live with when you associate with evil.
2) The alignment scale
I think one big complaint that keeps coming up is that it's hard for a paladin to get good and law points. You are right, and that's the way it should be. Think of alignment as a sliding scale. If you have 80 good, this is your level of expected behavior. There isn't much room on the good side, but lots of room on the evil side. It is difficult to do something so good, that it will shift you even more to good. You have to do something extraordinarily good to be "even more good". On the other hand, nuetral and evil acts are outside your current behavior, so it is easy to shift that direction. This is also true of evil people. Getting more evil points should require more vile and evil actions to continue to slide down. I personally have given good and law points before when I've seen actions out of the ordinary, or more commonly, actions by neutral characters where that isn't their normal expected behavior. So, if you are a paladin and want to gain law or good, you have to do something above and beyond the call of duty to do so. Have discussions with DM's on how to do so. I'm sure something can be arranged.
3) On discussing before shifting
To be honest, it's easier for us to shift first, and then let someone plead their case to get it back. At that point, it's in their court to convince us that the action was too harsh instead of us trying to convince them it was warranted. We do listen, but players need to remember that we won't automatically agree with them, and they have to be ready to accept that. I have given points back in the past, although more often than giving them all, I give a comprimise ammount.
4) Ammounts of shifts
We are trying to make it a policy to only do 1-5 point shifts at a time. This means it takes repeated offenses to actually lose your paladin status. You shouldn't be surprised if you actually lose status, as you've been working towards it for a while at that point. Now, if you commit active evil, that's different, and you will get larger shifts, usually resulting in immediate loss of paladinhood, just like it is deserved.
5) IC vs OOC
Remember, alignment shifts are an IC punishment, not an OOC punishment. Banning is an OOC punishment. You didn't get an alignment shift because the DM's hate you. You didn't get it because DM's are spiteful in general. You got it, because your character earned it through IG actions. Alignment is a character development tool, whether some people don't like the system or not. Alignment is given out like experience, although not as often, it reflects how the character is being played.
6) Fallen Paladins
What happens if you do fall from LG? Is it time to quit the character? No! A fallen paladin has a ton of potential for character development. Should they go evil in spite and apply for black guard? Probably not, especially as most fallen paladins will be NG. How will having divine blessings stripped away affect a character? There is so much potential to tell great stories here. So many interesting directions to go. Will they try to regain their status? Will they go on trying their best to follow the code, knowing they are unable to? Will they take up drinking to drown their sorrows? Will they stay good, but have hatred grow against the god who turned on them? Sure, you lose some of the abilities. However, if your whole reason for playing a paladin is the abilities, I have to be honest with you, not only is a paladin the wrong class for you, but you may be on the wrong server. The story comes first. Stats and abilities should be secondary.