What is the correct way to rectify this situation?
There is no textbook response. Whatever you and your attorney decide to do, you will be making it up.
Go back and look at the original check you issued. Verify where it was sent and whose endorsement it carries. It seems likely that the two firms must be located in the same place or even be affiliates. (It was an internal error on their part.)
If your check was delivered per the former customer's instructions, my suggestion would be that you return the item to the party who is offering you instructions and offer them some instructions of their own; e.g. "You converted the item when you had no right to, you need to fix the problem you created. We suggest you follow your own instructions and issue the check as ours was issued and deliver it to the correct party." CC the former customer.