Mouse stuttering or skipping randomly

EDIT:
ACTUAL FIX, AND YOU'RE NOT GONNA LIKE IT!

I've found that I only ever experienced mouse lag, when my RAM (memory) usage peaked, resulting in Windows being forced to do disk paging to cope with my lack of RAM. You can see if this is your problem, by hitting CTRL-SHIFT-ESC to open the Task Manager, and go to the Performance tab (do this just after a fresh reboot!!! See why below.). Leave it open, and try doing a lot of things at once (open a browser with many start-up tabs while opening some RAM-heavy program, like a programming IDE or a video editing suite). If it peaks, and your mouse subsequently lags, you probably need more RAM for your purposes.

This also explains why people can be posting so many different false "fixes". Whenever the lag occurs, because some operation needs more RAM, the data is cached in the page file. So when people have experienced lag while using their computer, and then do something to try and fix their problem, and try the same things that made the computer lag before, all those things are already cached, and therefore won't lag anymore...until you restart your computer, or the pagefile has been filled with new data.

The fix for me, ended up being installing more RAM. If you do not have that option, try to limit the number of programs simultaneously running on your computer. One way to do this, is by unchecking unneeded start up programs, using these steps:
1. Start ==> Run
2. Type in: msconfig
3. Hit enter the Startup tab
4. Untick all programs THAT YOU KNOW, which you do not need to have available at start up.

Another way, is to remember to close programs when you're done with them.

EDIT
Inspired by abandi's answer below, I'll include the possibility to change the way Windows caches your data. This may help a bit, but does NOT completely remove the problem.

1. Click the Start/Windows button and right-click on 'My Computer'.
2. Click on 'Advanced system settings' in the left-hand side.
3. Go to the 'Advanced tab'
4. Under 'Performance', click "Settings"
5. Go to the 'Advanced' tab
6. Under 'Virtual Memory' click 'Change...'
7. Now comes the customization, which will be different depending on what kind of user you are, and how much Windows needs to cache for you, in order to keep your programs running smoothly (again, if you're experiencing these problems, you need more RAM. This is a sort of workaround, using your harddrive as extra, slow RAM. Buy more RAM, if you want to fix this the right way).

For some, the best setting will be to have the checkbox 'Automatically manage paging file size for all drives' checked. For others, you may want to uncheck it, and set the values yourself.

Before changing anything, take note of the 'Currently allocated' and 'Recommended' paging file sizes at the bottom. These are the settings Windows is currently working with.

If you do uncheck it, and you have a drive in the list with 'None' as its paging file size (mine is my Lenovo_Recovery' drive), do not change the settings for this drive!

Now, Windows usually creates its paging files on the system-drive (usually C), which is also where all your programs are likely installed. It is a good idea to remove paging from the system-drive, and instead apply it on another drive, if you have a secondary harddrive. If you merely have 2 partitions on the same harddrive, this does not apply to you, and you might as well leave it on the C-drive! Also, if you have an SSD as your system drive, paging will work much faster when applied to this drive, but it will also eat away at the lifetime of your SSD, since page files do a lot of writing.

Select the drive you want the page file to be on, and select 'Custom size'. You will want to keep your 'Maximum size' of your page file AT LEAST at the size of the 'Recommended' indicator I told you to check earlier, and preferably higher. The higher it is, the more data will be paged, but that also means that your computer will access all this data much slower, than if it used your RAM, of which it doesn't have enough. Keep it sane. On low-RAM laptops, I usually set it to 8gb.

The 'Minimum size' is up to you, but there are pro's and con's depending on what you set it to. The higher you set it, the more time (minimal, though) Windows will spend filling it up while it is booting up. If you set it too low, you will see lag until it has been filled up. I usually set it to the size displayed by the 'Currently allocated' indicator from before, after a normal boot.

When you're happy with your settings for the drive, click 'Set'.

If you have more than one extra harddrive, you can chose to spread out the page files to more drives. This should increase performance.

Click 'OK', and you're done.