Over-a-year workflow issue finally gets closed!!

It's a big day in the history of my AX life. After over-a-year battle with Microsoft on a workflow issue, today we've officially got the issue closed!!! I'm not sure if this is the longest-open case in Microsoft AX history so far, but I've almost got thrown up on this marathon.
The client has AX 2009 SP1 on two AOSs. Business connector, IIS and AX settings were all configured. However, the following error got thrown randomly every other days and got completed workflow strandered. "Stopped (error): Failed to find workflow instance. Failed to find workflow instance."

There are several unique issues that make this workflow problem hard to solve:

• Error throws after workflow is completed.
• It seems errors randomly occurred. When there are a large number of workflows (> 50) being processed, errors are likely to be thrown.
• Hard to repro the error or test solutions. We had to accumulate enough workflows in the queue in order to trigger the error. It was a real pain by doing this all manually. Later, we wrote a script to simulate the submission process and it's much better.
• We have custom workflow templates.

The hotfix number is 2398999 in case you're seeing this error and don't want to spend another year on finding the solution :)