[Jeff Alton]

My suspicion is that flushing the gearbox will be successful. Was the coolant level low? Have you drained the transmission yet? If so, what did the fluid look like?

You don't have many options here. Follow the "plan" your shop suggests (not a lot of work in the big scheme of things) or replace the gearbox and still do some of the "plan" to get the oil out of the coolant. Let them do their thing and you will likely be just fine.

Cheers