Originally posted by Makosuke
The dirty sensor and possibly broken mouse that paulwhannel suggested are both possibilities, but one other possible problem is your mouse pad.
I say this because I have a gel mouse pad covered in black cloth (feels like some sort of soft nylon), and after some use, I eventually figured out that if I had my pro mouse lined up with the grain of the fabric on the mouse pad, it would work perfectly, but if I had it at an angle to the pad, it would start to skip and otherwise act up.
I'm assuming that this happens because on a microscopic scale the fabric acts as some sort of a funky reflector at certain angles, causing the mouse to mis-read motion when it is at a certain orientation to the grain of the fabric.
Your situation might be completely different, but I was convinced for quite some time that my mouse was getting dirty, when in fact it was just not straight enough, so to speak. Experiment and see if this might apply to you.