If you're looking into solvents, things can get a little tricky. Many are light, volatile and have very little surface tension, so they'll evaporate quickly, flow easily into any nook and cranny (even uphill through capillary action) - think acetone, isopropyl alcohol, lighter fluid, etc.
You may be able to get away with these if you're very careful and use single drops at a time.
Another thing that can work on wood and glass is oil (olive oil, vegetable oil, mineral oil, etc.) - general process for this is that you get oil into a small part of a cloth, then rub it into the sticker until it's soaked in. Leave it for a little while, then come back and wipe it off. If you do it this way, you have to peel off the sticker surface first, so it can soak into the adhesive residue. I'm not 100% sure this will work on plastic or with floppy stickers, so I'd try it on a spare broken disk first as a test.
Some other thoughts - test on a junk disk before using, of course:
WD-40 should work for the oil technique as well, but would probably be harder to apply. It's basically a magic adhesive remover on other surfaces, though.
Vinegar - it's a weak acid, shouldn't interact with the plastic. Might be effective vs. adhesive residue. You'd have to saturate the adhesive with it and let it sit for a good while (possibly reapply) though. Has the advantages of having basically the same physical properties as water, so should be easy to keep it out of the disk.
The general idea being to find a solvent that will work on the adhesive, but not wreck the disk. This may be harder than it sounds. I should try a few of these tomorrow...
If all else fails, use fire.