"Подумал через Timer. Но он по-моему не работает со службами." - но статья, на которую вы даете ссылку, утверждает обратное. Делаете ли вы в точности как в статье? Переменная таймера - поле класса, а не локальная переменная?

По поводу выбора между службой и приложением - это по ситуации. Смысл службы, чтобы все работало независимо от сеансов пользователей. Если этот аспект важен, делайте службу, а графический интерфейс будет взаимодействовать с ней через какую-либо технологию межпроцессного обмена. Если нет, конечно достаточно обычного приложения сворачивающегося в панель уведомлений.

Предотвращение случайного закрытия решается простым запросом подтверждения. Если не уверены, нужна служба или нет, сделайте ядро программы в виде DLL, чтобы можно было легко перенести в новый проект.

Кстати, если что-то в службе не пашет, это могут быть проблемы с правами доступа пользователя, из-под которого она запускается. В отличие от GUI-потоков, фоновые потоки, скорее всего, молча проглотят ошибку не выводя ничего ни на экран ни в журнал. Поэтому обработка исключений и ведение логов важно для служб.