@1101 in my experience, the best way to resolve these things is the most straight forward way. I have done this a number of times with success.

The easiest way is with the co-operation of the outgoing provider, so get their co-operation. Act as intermediatry between them. The losing service provider will likely want to be compensated for their co-operation, fair or not, and the best way is to come to an arrangement that YOU guarantee (we have even paid this as part of onboarding a client once). It's somewhat certain that the breakdown between the two companies was a two sided thing, but the customer's end result is what matters.

Call and speak to the owner of the LSP and explain what you need and ask what it would take for his/her co-operation. Be professional and firm, but polite because ultimately, you need their help.

Alternatively, if you have control over the domain, and I sincerely hope you do, export the mailboxes, set up a new tenant and import the mail.  It's probably as much work as a forced take over of a tenant.