And if the cost of (re)developing all the existing solutions exceeds the costs of MS licensing for a decade?

I find that highly unlikely given how much commercial agreements with MS costs.

But if that's the case then they should either look for a different COTS solution, and/or change their business workflow.

And in the event even that is unfeasible, then just continue to keep a few windows machines (maybe convert them to VMs or VDIs for ease of maintenance) for the few users that can't be migrated.