It has taken me many years to fully understand what is going on here, but the Publish button on the starting rule is more like a save button. It does not publish the rule to the subscriber, it just saves the rule. The rule is not published to the subscriber until you open the workflow and click publish.

One way to see that this is true, besides just noticing that your rule doesn't work after publishing, is to have a workflow server with no starting rules of a specific type, like entry moved for example.

When this is the case, while viewing the subscriber log for entry move instances, it will say "No Starting Rules" because there are no starting rules published for an entry move, so it has nothing to compare against.

Now find an existing workflow, create a starting rule for entry moved, and click the button that says "Publish". Now move and entry, then view the instance in the subscriber log, and it will once again say "No Starting Rules". This is because that "Publish" button only saves the rule, it does not inform the subscriber.

Now open the actual workflow and use the publish button there, to re-publish the workflow. Now the new entry move rule will be published to the subscriber and it will see the rule.

I would like a Save and Publish option for new rules, so that we can enable them without republishing the workflow.