Adding a registry entry to remap keys is pretty trivial, too.
You need to be an administrator to do that. That makes it pretty non-trivial.
It would, except that users having Admin access is much more common on Windows systems. (Being an Administrator on Windows does not (in theory, at least) have the complete "game over" privileges that "root" traditionally does on Unix-based systems, so there are still further privilege levels to be escalated to.)
is running a different OS which doesn't treat Ctrl+Alt+Del in a special way
Now your suggesting what exactly? That the attacker is going to throw in a linux live CD, boot it, run his 'fake login screen' that looks like the usual windows screen?
Ok... yes I guess that is a theoretically possible attack; although you'd probably get caught as soon as the user isn't actually able to log-in and IT gets called in...
Why would IT get called in? After the user's entered their password, you just display a simulated BSOD and then reboot into the genuine OS; no user will be remotely suprised ;-)