Apologize for the complete quote, but there is a lot in your post to comment on.
Agreed, software should give better logs, but that goes for the installer as much as for Windows or AV programs; it's not "my PC", though, nor am I running outdated or flaky hardware...
As you correctly concluded, the "culprit" in this case was indeed DEP. Changing the setting to "DEP for Windows and system programs only", (instead of enabling DEP for all executables) and rebooting did the trick.
This time I carefully monitored the installation and checked the installer log. I noticed that the installer actually never writes to the Windows system directory and after installation, "Runservice.exe" still does not show up there. Only after the program runs for the first time does "Runservice.exe" magically appear in the system directory, as well as additional files "mmfs.dll" and "lcmmfu.cpl" (both "Copyright © 1998-2005 ViaTech Technologies Inc."). So it's not really the installer that's not working, it's DEP (legitimately, I think) preventing the program from running after installation when it tries to do something fishy.
Seeing this, I'm not surprised the install is not working, DEP is likely working as designed by preventing execution of something that was treated as a data file before (e.g. by copying it into the Windows directory). The copyright notice also makes it pretty clear that the licensing technology pre-dates DEP (and UAC) and thus is not designed to deal correctly with modern OS security. I'm also not thrilled by it installing what is basically a fake control panel plugin and mucking about with Windows Update (got an unexplained log "AU received policy change subscription event" at install time). If I had to conclude anything about all this, the culprit is really an outdated installer and licensing software that behaves in very suspicious ways, not the OS protection mechanism.
I don't think copying only runservice.exe to the Windows directory would work; at minimum, you'd also have to copy "mmfs.dll" and "lcmmfu.cpl". They probably also make other changes to the system.
I think your comments regarding UAC and DEP are pretty misplaced. Requiring your users to disable OS safety mechanisms to install a game is just no longer an acceptable policy, IMO. UAC may be annoying, but certainly much less annoying than catching a root kit, trojan, or other malware infection and having to wipe your harddisk and reinstall everything.
Overall, I think the "problematic behavior I'm seeing" is EXACTLY in "your code", not in my PC (hardware or software). I agree, "It's bad programming really...", but not in the OS for once.