Compatability mode mentioned by BlueFire, you can also right click > properties, and change Compatability mode to various windows versions, can experiment with it, althought this should affect GTA SA as a whole, not only SA-MP.
If you have a other drive than C:\ you can try installing it on that drive.
If you got dual monitors, might aswell plug one out to see if that'd fix anything.
You should ensure you're using the correct SA-MP version
If your game is torrented, might aswell experiment by DLing another torrent.
After installing CCleaner, CCleaner starts on boot. You can disable it in the program settings (or Control + Shift + ESC and "autostart"-tab), I've had issues with CCleaner interferring with punkbuster or something prior.
Your GTA SA documents folder (mine is at "C:\Users\my-name\Documents\GTA San Andreas User Files") doesn't change althought you reinstall GTA SA, and there are some samp-related files there (atleast specificly gta_sa.set). I'd recommend renaming your "GTA San Andreas User Files" to something, and then reinstall GTA SA & SA-MP, so you get a fresh version of this folder.
SA-MP has saved your GTA SA path. Ensure your SA-MP client goes to correct path by opening samp, press the "Tools"-button in the top bar, and the "Settings" option in the dropdown. It goes to the folder, not the .exe. e.g. mine is <drive>:\Activision\Gamee\GTA San Andreas1234\Installations\GTA San Andreas (GTA San Andreas is the folder where my gta_sa.exe is located, thought.)
If your game is torrented, ensure you're using the correct crack, there's a lot of versions, 1.0, 1.01 NA/EU? I dunno which one is the right one, thought if you havnt changed crack since your game was working ignore this.
also make sure you've uninstalled all SA-MP installations before re/installing SA-MP
Can also try disabling DEP (google it)