Службы не должны взаимодействовать с пользователем рабочего стола, поэтому они не должны быть в состоянии отслеживать нажатия клавиш. Это может работать в XP, но у вас, вероятно, будет много проблем в Vista / 7 и более поздних ОС.
Вы действительно нуждаетесь в пользовательской программе, которая запускается при запуске пользователя, чтобы сделать это, и она запускается под тем же пользователем, что и вошедший в систему пользователь.
Кроме того, если вы беспокоитесь о минимальной занимаемой площади и использовании ресурсов, вы не хотите использовать .NET, поскольку ему требуется загрузить довольно большую библиотеку времени выполнения и создать довольно большой рабочий набор. Обычно это не проблема, но для чего-то вроде программы-наблюдателя лучше написать ее на низком уровне C, используя минимальный запуск CRT.