Good idea about the restore point. Deleting it from the Start Up list only "removes" it from starting up. It doesn't actually delete it. And many of these "things" are clever enough to insert themselves back into the Start Up list and start up all over again. Just an endless game of whack-a-mole.
Utilities like HijackThis (there are others - this is just one I'm familiar with), will tell you who the publisher is of the executable (can be faked but you'd be surprised how many don't bother), the location and when you hit delete it removes the exe's, the DLL's and the registry entries too. The whole kit and caboodle.
If that doesn't fix the issue - then you are likely in RootKit (and similar exploits) territory. Although it doesn't happen as often as people are led to believe - it requires work to build one and tie it to an exploit (usually a zero day one), so most script kiddies stick to these sorts of "easier" pieces of rubbish that stick themselves in the Startup list.
Been a while since I had to use it - I think there is an option to "record" or "backup" what is being done.