Sympton:
1) any publishing workflow failed with the same error, but none of non-publish workflow failed
2) they failed on every site collection in the web application
3) they did not fail to another web application even when the site is also a publishing template
So those symptons make me think the problem is at web application level, and maybe publishing features related. For that reason, I deactived and reactived all features at applicaion level, and also tried deactivate/reactivate publishing features at site collection level (even it doesn;t make sense, but you are willing to try everything when desparate, aren't you?). I also made both applications share same application pool. But none of those effort as well as server reboots helped me find any clue.
The ULS viewer showing the following 2 errors:
RunWorkflow: Microsoft.SharePoint.SPException: error compilererror Line="1" Column="1" Text="The root activity type is invalid." /Error
at Microsoft.SharePoint.Workflow.SPNoCodeXomlCompiler.LoadXomlAssembly
Microsoft.SharePoint.SPException: error compilererror Line="1" Column="1" Text="The root activity type is invalid." /Error
Which doesn't really help after spending hours on Bin.com.
Finally another ULS error shed light on me:
Microsoft.SharePoint.SPException: An error occurred creating the configuration section handler for System.Workflow.ComponentModel.WorkflowCompiler/authorizedTypes: Could not load type 'System.Workflow.ComponentModel.Compiler.A uthorizedTypesSectionHandler' from assembly 'System.Workflow.ComponentModel, Version=3.0.0.0, Culture=neutral, PublicKeyToken=31bf3856ad364e35'. (C:\inetpub\wwwroot\wss\VirtualDirectories\80\web.config line 20)
The resolution is then very simple: open web.config and fix the typo there.
The question I need to ask myself is, how can I miss this ULS error earlier? The reason turns out to be, this error occurs when a workflow is created, not when the workflow is running.