Roof Decking: Plywood/OSB over skip sheathing (decking) or should I strip to the rafters?
Skip sheathing for shake roofs used to be really common around my area of the country and I've never removed it (or seen anybody else remove it for that matter).  OSB or plywood over skip sheathing makes for a much stiffer roof deck, resists problems with expansion better, and obviously doesn't require all the hassle of removing it. 

After you strip the roof, do spot repairs to the existing sheathing where needed, then go right over it.  You'll want to use both longer sheathing nails and longer roofing nails.  The sheathing nails should be long enough to give a good hold in the studs, and the roofing nails should be long enough to penetrate both layers of sheathing.