C# – I would like to create Visual Studio deployment project that creates some scheduled tasks in a domain environment

You're seeing the result of session 0 isolation. Essentially your scheduled task was exploiting a security hole in Windows that was closed in Windows Vista (and your scheduled task itself might have represented a security hole).

You can configure your task to run as the interactively logged on user which should probably resolve your issue.

Follow like this:

1. Type in secpol.msc /s
2. Select "Local Policies" in MSC snap in
3. Select "User Rights Assignment"
4. Right click on "Log on as batch job" and select Properties
5. Click "Add User or Group", and include the relevant user.