Guys, I've just managed to make it work with the Kaspersky Internet Security suite (latest version) installed on Windows 10 Pro x64 Version 1607 (Build 14393.447)!
I've already tried this method earlier, so I think it's related to a recent update of Windows, Kaspersky or Sandboxie.
First add *everything* that is related to Sandboxie to the exceptions/trusted programs of Kaspersky. All folders, all executables, all dll's, and also the installer.
(I've already had this set up from one of my earlier attempts)
1. Remove network cable
2. Quit Kaspersky from system tray (don't forget to set up all the exceptions first, and maybe reboot)
3. Install Sandboxie (most recent version)
4. Try to run something in the sandbox, except Microsoft Edge! (more info later) The endlessly looped message about the "not implemented service" should be gone!
(not sure about the english terms - I use the german version)
5. Resume Kaspersky
6. Insert network cable
I've tried to get it to work so many times... Especially because this issue wasn't present earlier. I've used Sandboxie for quite a while together with Kaspersky. Finally I can use it again, that's awesome! I really hope this works for you too, guys!
What made me a bit curious, is that when I started a program in the sandbox for the first time, I got a strange report from sandboxie that I've never seen before... There is "not enough space" and "click ok to increase it" or something like that. It was a very small increase, something like from 57812 kb to 57844 kb.
Can't remember the exact wording and size, I've kind of rushed through it. However, after that everything was working fine.
The only thing I've changed on my PC since the last time I've tried to get Sandboxie to work, is installing a "RAM Cache" program. (Primo Cache)
That's a program to use some of your RAM to increase disk cache, to speed up read, write or read+write performance. (I use it in read mode)
But I hardly can imagine that this has anything to do with Sandboxie. But if - then it could be the reason for the strange "increase space" info, and/or maybe it could also the reason that it works now with Kaspersky? If my described method doesn't work for you, try to install the demo version of Primo Cache, set it up to read mode on all internal drives, and tell me if it worked!
About Microsoft Edge:
When I tried to run it in a sandbox, the Edge process (iexlore.exe) has frozen, and I couldn't run the Windows Task Manager anymore. It just didn't launch when trying to run it from Task Bar. (via right click)
And the screen that appears when pressing ctrl+alt+del didn't appear anymore. I've also tried to kill iexplore.exe from a third party Task Manager, but access was denied. And the reboot command also didn't react. I had to use the reset button on my tower.
After booting up I've tried it again, with the same result. This time there even was a check disc on reboot, and I had a strange lag of about 2 minutes after booting, before I could do anything. Luckily, everything went back to normal after a while.
So I recommend to not try it with Edge... All other browsers I've tried - Chrome, Firefox and Vivald - were all working perfectly fine.