Я сделал это c # 3.5 с WCF. Вы можете запустить exe из веб-службы. Exe будет запускаться на компьютере, на котором размещена служба, и с пользователем служба настроена. Вам нужно только написать нормальный Process.Start (...) код.
Так что ответ - да, вы можете, и, конечно, exe будет работать на хосте веб-службы, а не на клиенте. Если вам нужно больше деталей, будьте более конкретны в своем вопросе.