Windows 2003 Task Scheduler Problem

I'm having a problem with the Task Scheduler on a number of Windows
2003 boxes. (The machines have had various hotfixes and security
updates applied, but no service pack).

The Task Scheduler log is full of messages like the following:
"Build_SP.job" (autodeploy.bat) 2/14/2006 4:30:11 PM ** ERROR **
The attempt to retrieve account information for the specified task
failed; therefore, the task did not run. Either an error occurred, or
no account information existed for the task.
The specific error is:
0x8004130f: No account information could be found in the Task
Scheduler security database for the task indicated.

When attempting to modify the Run as: information for the problem task,
the following error dialog appears:
An error has occurred while attempting to set task account information.
The specific error is:
0x8007007a: The data area passed to a system call is too small.

The security credentials being used are for various domain users who
are members of the Administrators group with non-blank passwords. The
same error results when trying to create a new task on the affected
machine (meaning the Task Scheduler is completely inoperable).

It seems like a number of people have encountered similar problems, and
I've tried every solution I could find online. Restarting the service
and waiting 15 minutes for a clean-up process doesn't work. I've read
solutions involving deleting cryptography keys out of the registry and
restarting the machine with all 3rd Party services selectively
disabled, and nothing has resolved the issue on the affected machines.
Also, only some boxes are affected. Other similar boxes can have the
same tasks scheduled with the same users with no problem.

If anyone has any insight, it would be greatly appreciated. Thanks very