It also does not work on Invoices generated by a workflow.

Do you have the Workflow running on those contexts?

Yes, I do. It is set to run on all contexts right now. Both the workflow and the action.

Check if the Invoices generated by the workflow matches the condition you set, if there are any, in your other workflow

Yes. They do. If I manually bill the same invoice sales order I am testing with, it works.