I came across this issue yesterday when debugging the test environment for my current project.
I decided to tidy up the execution order for the many plugins we have written on each entity. I then exported the managed solution from dev environment and updated the test environment.
I found out that in test environment there are duplicate steps for the same plugin/entity/message with different execution order.
I think that because the step id is different on both environments, crm figured out the plugin step signature from the configuration including the execution order. Since the execution order is different, this causes the issue.
Cheers – Sy