During a campaign as the Saxons I got a christian leader (note to self always check religion no matter the number of stars). It seemed before I new it I had three christian generals causing characters in region and faction leader religion problems. I put all christian generals/faction leader into to one small fast moving army. They almost wiped out a mid size Celtic army by them selves.

Or...

If the problem is severe the generals with the wrong religion could go for a boat ride. It won't gain you anything but it is quicker.