We are successfully using scheduled external tasks to create Remedy service requests, but did run into similar issues. For us it turned out to be a conflict in Queue calendar hour settings. Setting all queue calendars related to the process to 24x7 seems to have resolved the issue for us. I hope this was helpful.
In trying to provide a complete answer, I thought I should also add that the queue calendar changes will, of course, force updates to tasks durations for any tasks assigned to the queues you have changed.
We just went through this too. If the plan is fairly complex, and has allot of conditional tasks you will have difficulty.
The explanation I got from Shweta is that the calculation that determines the OLAs before my scheduled task was to start looks at ALL the potential tasks and combines them, essentially saying the duration is much longer than what you think it should be, ie the sum of all potential task OLAs, not just the tasks that became active.