Is the core "brown mush" that you're removing? Is the deck skin delaminated? Does it give when you walk on it?

If 'no' to all of the above, you may be able to get away with drying things out, resealing the holes, and then sealing up all the avenues of water ingress before you paint.

On the other hand, since you're repainting the decks already and have everything removed, this may be a good time to do a recore and have that job behind you. It sounds like you may only have to do a couple of spots anyway, not the whole thing.