How to restart the Task Scheduler service without rebooting the server

Congratulations! You've come up against a problem that has stumped many a Windows user/admin. No, you cannot rename a task except for exporting, renaming and importing again. Yes, it's rather silly. Perhaps an enterprising scripter could create a simple PowerShell script that automates this, but until then, you're stuck with your export/import two-step. Sorry. =(

(You also can't rename a task folder after you've created it.)

When you say "we simply re-enter the same exact password" I think you're really saying "We reset the password on the account using the same password". I don't think you're saying that you're changing the password stored in the "Scheduled Task" entry.

If that's correct it sounds to me like the account's password is expiring. By resetting the password you're resetting the expiration countdown, too.

If the account is an account on the local machine where the task is running using "Local Users and Groups" to mark the account as "Password never expires". If the account is a domain account you'll need to make that change in the Active Directory.

Examining the security policy (either on the local machine or the "Domain Security Policy", depending on where the account is located) is going to tell you what the password expiration policy is like. It seems the most likely explanation that password expiration is the cause of your issue.

Edit:

Per your comment and edit it sounds like my "psychic powers" have failed me on this one.

I think I'd fall back to making a copy of the ".job" file from the %SystemRoot%\Tasks directory that corresponds to the problematic task and using a file compare utility when the problem crops up to see if the task definition file is actually changing. If it is, then auditing filesystem access to the file may be able to pinpoint the cause of the change.

If the file isn't changing then you've got me stumped!