Without being able to ask for clarification on your question for the surface on which you use your mouse, I would suggest replacing the mouse pad or not using one so long as the surface is a relatively uniform colour.
In older versions of Windows (I'm sure it'd been fixed in XP) there used to be a problem in which something would hook into the pointer and cause it to move as an adjustment or attempted fix to the pointing device's movements... As random programmer mentioned in his comment on the question, applications can modify the pointer position. There could be something installed (even a driver) which is causing this issue.
Have you installed any drivers or software specifically for your pointing device? A convenient way of checking whether there is any software causing this, is to boot into Safe Mode and see if the problem still exists.
Another suggestion is to plug the mouse into another computer or laptop and see if the problem recurs. If you can, use it on the same surface that you do on your computer. I know you've already mentioned that you have replaced your mouse and have seen no change in behaviour, but it would be good to eliminate your mice (computer mouses?) as being problematic.
- Try a new mousing surface (such as a new mouse pad, none at all or a piece of white paper taped to the desk if necessary)
- Boot into safe mode and see if it still happens
- Uninstall or update any mouse drivers or software you have installed
- Try the mice/mouses in a different computer/laptop but on the same surface/table/mouse-pad and see if the problem recurs
EDIT: Are the mice wireless? There could be interference from another wireless device such as a network router, wireless keyboard or naturally recurring radiation....