Ran into this interesting problem today. It is related to this long running workflow bug from this post. As part of the eBay/PayPal split, we are creating a new domain and moving the users. Of course, some users still exist, some do not. No matter what, the workflow user will not exist in the target domain. So the previous bug occurs.
But we ran into another issue. All the listsite workflow associations disappeared for those "User not found" workflows. Took a couple of hours, but finally figured it out.
If you run the SPFarm.MigrateUserAccount method before updating the non-existing workflow owner to an existing person…you will LOSE ALL ASSOCIATIONS for all the workflows across the farm that the previously migrated user owned! Ouch…
Lesson learned…be sure to update the workflow modifiedby first, then migrate your users!