I think a better idea is to tie the hiring of certain mercenaries to Faith Points. And an increase in the number of mercenaries to compensate for this.
For example, hiring Templar/Teutonic Knights should require a high enough (>40) Catholic Faith Point, whereas hiring Lipka Tatars (who are Muslims) should require a low enough (<20) Faith Point. This will make Lithuania and Poland hire them more easily, but still allows access of other civs. This will also prevent Teutonic Order from hiring them easily, as Teutonic Order should start with a very high (40 to 50) Faith Point. But instead of Lipkas, the Order State should be able to hire extra Teutonic Knights (Sword Brethren) that become available in Livonia, Prussia, and Estonia.