I guess so. That wouldn't be "political rivalries" though. In that case, he would basically be another Rosier the Fallen.
How would he end up a Malakim leader though? I guess I could see an Order crusader man who failed to live up to the letter of the law finding a safe haven among the Empyrean, but I don't really think it is likely that such a man would rise to prominence there. In my version he wasn't banished or found guilty by the Malakim though, he simply chose to side against them.
The main reason I chose Malakim->Bannor->Calabim though is that going from Bannor to Calabim seems a much more likely transition than Malakim to Calabim. If he had started as a Bannor and sought refuge from the wise man of the Calabim then I'd tend to emphasize with him much more (the Order laws were probably unfair to begin with), and find the defection to the Calabim hard to understand. Going straight from light to darkness seems less likely than falling slowly into corruption and fanaticism.
I guess I could try to come up with a scenario where he didn't end up Calabim, in which case he could turn to the Empyrean eventually and be redeemed. Of course, not allowing such redemption would probably fit better in a dark fantasy. I don't really see him as being that Heroic. Also, if he was the leader of the Calabim he almost certainly became a Vampire. The desert sun would probably be too much for him then, and I don't think there is a cure for Vampirism.
Who says the Order and Empyrean existed during the time Decius changed sides?
But say they did. Empyrean is a religion that would shelter political and war refugees. Just like a neutral country like Sweden did during the WW2, and still do today.
My reasoning for him starting in Bannor is they are probably the first nation to get a standardized organized Army in the age of rebirth. Being forced into a war against the orcs early, and having combat experience from hell. Not to mention being led by an Organized leader already. To me Decius was probably a commander/general in the Bannor vs Orc war. Once that war settled down, and the Embers was formed, he wanted more enemies. The other generals wanted stability and to build up the Bannor civilization now that they finally had peace.
In some way or another, Decius does something controversial at this point. Like leading a band of loyal soldiers to war against some sovereign empire without any ok from the above leadership at all. Trying to force a war which his leaders do not want.
At some point Decius gets taken care of and has to flee. He finds home in the Nomaic Malakim. This might be pre-Varn. Or maybe early varn. They might still be nomadic, without permanent cities. For some reason, through his political and military prowess perhaps, he climbs through the ranks and gains a high seat of power.
Eventually, he gets driven away from Malakim as well, and then finds a permanent home in Calabim, where they appreciate his deterministic warfare style. I would guess he becomes a good friend of Flauros and maybe a lover of Alexis for a while.