Oh!! its SharePoint again :). One of these small things in this beast which makes you bang your head and pull your hear again and again if you don't get it right. Now lucky you you can search this issue and find the solution.
Debugging in SharePoint is very tricky sometimes because you get all of these levels to run around (GAC + IIS + Deployment Folder under the feature + Feature.xml + Workflow.xml + SharePoint itself + InfoPath the main form template + InfoPath the workflow forms and Web Services) so after this, it is not strange that you would start pulling your hear after a while.
if you try any workflow (including OOB WF and Custom WF) and when you try to start it, it will show the message Workflow "Failed on Start (retrying)". You may also see that some tasks in the WF are created and even so it fails.
Tip: whenever you are stuck with your custom workflow, try having the OOB, if it doesn't run, its not your problem. (i spent one complete day almost 20H just to discover its not my fault).
One Proof that this thing its not your custom code problem, if you attach the WF process to Visual Studio, it will not catch any exception.
In WSS/MOSS the workflow engine will report back 'a workflow failed to start' even if the workflow did start.
The reason why is that - the workflow will be sent the 'OnWorkflowActivated' event (start command) and essentially as far as MOSS is concerned - it's starting.
When the workflow for e.g. writes a task item and then waits (handleExternal Event) for the OnTaskChanged event. At this point if it failed - a different error other than 'failed to start' would be reported.