Gavin is already trying to solve this with Bitcoin and any improvement could be forked over to CryptoNote.
I don't see how what Gavin is doing applies here. Different technologies. One Bitcoin transaction is recorded as one transaction, not n mixins.
I could be wrong, but I'm pretty sure typical blockchain pruning methods that might work on Bitcoin don't work on the CN coins. The developers are going to have to invent novel ways to reduce the size. Although I've heard it mentioned that anything more than linear reduction is probably impossible, but that was a while ago.