General question: how much would one of these services cost? Any references to any?

It depends heavily on target, architecture, used programming languages, binary size, if the binaries were stripped, etc. From $1k to millions.

Would that be legal?

Australian lawyers from the top of Google Search results say that it can be if done careful:

> Generally, where a computer program is reverse engineered by copying the idea of the function presented in the program code, the original computer programmer’s copyright is not infringed. Where a computer program’s expressions in code are reproduced or adapted (including into a different computer programming language), the original computer program’s copyright is likely to be infringed. This means that where reverse engineering occurs by “clean room” design, Australian courts are unlikely to find that there has been an infringement of the original author’s copyright.

Source: https://www.dundaslawyers.com.au/reverse-engineering-of-soft...

It is is their own code, why not? In the worst case there is always clean room reverse engineering.