Can clerics, paladins and followers of enemy and unfriendly deities interact and associate? Absolutely. Can they travel together? Of course. Can there be mutual respect? Surely! Should they be all hugs and smiles? Absolutely not. Should there be an ever-present tension? I'd say that would be appropriate.
Now whether its BAD RP or not, I'm not gonna say, but each situation should be looked at first before some kind of punishment, retribution or whatever is dealt.
I think another twist on this is the alignment and dogma of the specific deity. For instance Toran is a compassionate god with an emphasis on forgiveness and restoration. There is a particular Mistite who has declared that she would watch Clarissa bleed to death before healing her. That's an understandable RP from the Mistite perspective but when that same Mistite was trapped in the bottom of the rift and needed rescuing and ressurecting a couple of Toranites came to her aid since it is in their dogma to help others in need. The Toranite perspective would still be one of tension since it would be understood that there would be no recognition of the sacrifice involved and no thanks for the help but would feel pity for the one incapable of understanding the importance of that compassion. So there is still tension on both sides but different actions are both justified based on the dogma of the deities.The botttom line is that deity relations and personal relationships are very complex. In RL there are lots of people who are friends that have divergent beliefs. So it depends on whether the situation is asking your character to act against your deities dogma or not as to whether a particular action or friendship should be avoided.