Did you change the mousepad recently, or otherwise alter the surface that the mouse is being used on? Also, when you say that you keep it clean. Are you blowing it out with air? I've found that isn't always good enough, and sometimes I need to get in there with a q-tip and scrub the lenses.
When you say optical, I assume you mean optical without a ball. LED driven? Could be that the LED is starting to lose output and just doesn't have enough power to get a good enough reflection to track. Generally LED's don't fail, but instead they start to fade. Sometimes changing the mousepad will help, if the color on the current one doesn't get enough contrast.
