I'm in a game as the Mongols now on Immortal difficulty and I'm finding it very easy to annex CSs by the mid-game. Once my army was around the global average in strength all I have to do is move a force near a CS and I can annex them. I'm not even having to DoW and kill their units first. It's possible that if they had an ally or a pledge of protection then killing their units would be necessary, though.