If it's established in your game world that creatures commonly do not match their inherent racial alignments then I can see something like this happening. If red dragons have saved villages from the ravages of tyrranical golds, and demons patrol the roads to keep travelers safe from the evil bandits...If this is not the case, than any attempt to do something like this would probably ruin a game for me(as a player). I don't think I could reconcile allying with a demon, since they are ALWAYS evil by the core rules...evil literally runs through their veins and gives them the evil subtype. For the briefest of time I can see remaining unfriendly towards one, say if they wanted to kill the same group of bad guys as us....even though they would be killing for power and greed and to furthur some evil agenda, while we would be fighting to save the prisoners etc...But the second the battle ended I would be ready to turn on the demon at the slightest hint of aggression.
In a world like ebberron where its established that pretty much all creatures can have varying alignments I could see it working. Otherwise, no way. Either the good characters would have to breach their alignment 'codes', or the succubus would have to go. In the clerics case, you'd be right to revoke his spells until he made ammends. This is especially true if anyone outside of the group found out they were traveling with a demon and word got out. Even if the PCs could find a way to rationalize a way to travel with critters that generally enjoy tormenting and torturing the weak and destroying all that is good in the world, the rest of the world likely can't.