Elf Witch, I think your Paladin is acting the right way. After all, in order to become a Paladin, your PC took oaths of loyalty and duty and such. Well, who did he make those oaths out to? I assume the King-In-Exile, and not the "Host King".
At my table you would be playing it right.
On a side note. If the Host King takes your character in, and specifically assigns you a mission and you agree to take that mission on, and then the Exile-King comes to you in secrecy to preform some other action that is counter to your previous obligation, then you have a moral problem. After all, your character made an agreement with someone, he SHOULD try and KEEP his promises...that's a personal thing. You have a oath of service to the Host King: You made a deal with him. On the other you have a duty to the Exile-King, whom you owe fealty. You have given your word to both, your honor is on the line to both men.
At some level I have to say, "Shame on your King." for putting your Paladin in this position. I could see this changing your dynamic with the king in a personal and professional way. After all, can you serve a man who would be so dishonest? Or is he honest and the enemy is dishonest, which means then you have to ask yourself, is usuing the tactics of the enemy the way to truly fight him? Do multiple "wrongs" make a right?
This is a PERFECT moral dilema for a GM to throw at a Paladin PC. He's right in following either or both or neither men's plans for the sake of "doing the right thing by his own personal moral feelings." Not everything is about following the orders of a King, Kings can do wrong, and a Paladin is obligated to think for himself for the better of all over the crown. Say a LG King suddenly orders a village burnt to the ground but won't say why to the Paladin. Does he blindly trust in the King and perform the act or does he investigate the matter and essentially refuse the orders given to him by his lawful master and king whom he has sworn oaths to?
By essentially cheating and lying (after the fact) to the Host King, he makes a bad name for himself and for his people and his King to the Host Kingdom.
Good stuff.
As other have said, I would have a sit down with your GM. Explain WHY you think your PC is in the clear and HOW you percieve the oaths and honors of a Paladin are set. I say be firm in your conception of your character, it is your GM's fault for not setting that clear with you at the start of the game.
In any event, I applaude your steadfastness and comment about taking the fallen paladin / avenger route if your GM is "a jerk" about it.
Good luck.