That's bull**** that the original masters for many of the episodes don't exist anymore. Complete and utter bull****.
The original uncut masters, along with the original 35 millimeter interpositives and 1/4 inch audio tapes, are housed in a Hollywood vault set up by Michael. This has been confirmed by a fellow named Rick who runs the Highway to Heaven Homestead, the unofficial fansite for the series.
They just did not want to go back to the original elements at all.
Whoever said there weren't original elements somewhere?
But you are right they didn't go back to the original elements or masters. My take is because they weren't available to them or that the cost was to high for their company. If you look at a typical Millcreek release you will see they get access to something already prepared and ready to go out. All they do is repackage the episodes and release for a cheap price.
Other than the studio's how often do these small distributors take on the heavy lifting costs for a release? Take for example, the Peter Gunn release that was available in the UK. Someone found a decent set of prints and prepared them for release. The company was bought or merged, the prints became available for licensing, and Timeless picked them up for a US release. They didn't do a lot of work on them other then to author them to DVD. HWTH is similar in that they were also prepared for release in the UK. I'm betting Millcreek just made a deal to get the same prints and release them in the US at a low cost since the previous US release was so expensive. Do they always know what they have? Nope, they are just in the business of quick turnaround releases at a cheap price.
The shame here is not Millcreek itself, but that someone bigger didn't see HWTH as an opportunity and do a release that we as fans could appreciate by going out and getting the best prints available. The fact that the previous release probably didn't sell well (most likely due to high price and cut episodes) didn't help matters.