We had the same problem in my Mom's 94 L Sedan. At first we thought it was the cds I made, I made all new and used some originals-still skipped. My dad took it to car toys to get it cleaned. All they did was use one of the cleaning cds you are talking about. My dad finally got fed up and just bought new, that is what you might have to do.
When I first installed my alpine chms620, it skipped on every little bump. So i took it out to return it when i noticed that there were TWO shock absorber setting on the changer - i had originally only set one side for vertical dampening. After I switched both switches to vertical dampening (mine's installed in the factory location), all skipping problems stopped. Not sure if this is your problem, but if it is, its an easy fix.