I'd like mercenaries to convert and/or change their hiring restrictions when the religious landscape changes. I mean it's fine the orthodox guys have their own exclusive merc gangs, but when said gangs remain the
only orthodox people on earth patriarch notwithstanding, they aren't gonna starve out religion or not, no?
Since all have a "capital" attached, it could be tied to its state. If a capital gets converted to another religion, merc leader gets a choice to convert or move out. First case, either parent_religion is changed or hire_trigger religion condition is removed or moved up the religion tree to allow competing branches. Second case, capital is relocated to the nearest province of proper religion. If religion is dead and there is nowhere to move, the company either converts or disbands.
Same could be used for culture, the varangian guard must feel awfully lonely being the only swedes in the cruel danish world