Yeah, wow. That's obnoxious.
I think you and your DM need to get something straightened out: In the default D&D ruleset, paladins are Lawful Good, not (lawful) and (good). LG is a term of art, and in effect, it refers neither to law in the legislative/regulatory sense, nor to good in the purely relativist sense. Even though a denizen of Karrnath might think that it's "good" to partake in vampire blood feasts, that doesn't mean that it's Good. Likewise, just because the laws of Breland protect Breland's citizens from outlanders, doesn't mean that following them constitutes Lawful conduct.
Thus, while it is possible to have two paladins serving opposing powers, if one of those powers is "right" in the abstract D&D moral universe, and the other is wrong, then one of those paladins isn't going to be a paladin for very long. For example, if your Brelandish (?) paladin believes that protecting a man who has committed thousands of human rights violations and murders is "lawful" and "good"... well, he can go on believing that in character, but such conduct is neither Lawful nor Good in the D&D sense.