I just don't understand what all of the fuss is about. Preach out the enemy dominion and the problem is solved. You should be able to surround his cap with temples and move in your own prophet or god to speed things up. Remember that you can change sieging priests orders to preach as well.
In the mien time, just maintain enough of a force to protect your hold on the province and protect the preachers, then move on with your main force to more juicy targets.
