Ok, an update. I found a blog post regarding stuck workflows in SharePoint, which were related to a hotfix applied a few months back. Basically, items created with system accounts won't start automatically without changing a workflow property on the server. A stsadm command needs to be executed on the server as such:
stsadm –o setproperty –pn declarativeworkflowautostartonemailenabled –pv yes.
While this solved the issue of my workflow getting stuck in the Started state, I still have an issue with new items not starting at all. Anybody have data on this issue? Please help, I'm stuck and need to get this solution into production.
Thanks.