Steam (and others) really should scan for that kind of spyware in the files they provide to the players. Add a warning maybe (Contains a known spyware) or flat out refuse the editor to bundle that file with their game/app/whatever.
That's a service I'd actually pay for.
I bet intercepting some syscalls + running as another user might go a long way without affecting performance that much.
One of the ways malicious people circumvent that is to leverage the scripting that many of the games support. I have dug into many games that use LUA scripting and have appalling security practices. The worse offender is Garry's Mod. Trivial to dox players and fairly trivial in some cases to take over the players machines.
Give apps a secure sandbox by default, and require them to prompt for any external or 'dangerous' permissions. This gives ultimate control to the user.
Another idea would be to make an exception in the copyright law to allow anyone remove spyware or offer such services.