Not where I'm from. I will test, adjust, test again, adjust, and test yet again before pulling new MV cable. Big player or not, the cost of new MV armored cable and the labor required to install it (and remove the old) can be prohibitive unless tackled as a last resort. And regardless of the company name, they are probably not made of money in today's economy (oil companies not withstanding).
The fact that the cables "meggered" good when the stress relief was removed would indicate a possible stress cone failure, caused by moisture or some other contaminate or condition. It is not unusual for a stress cone to break down months or even years later due to improper cleaning or installation. Stress cones do just what the name implies; they relieve the effects of corona, or stress. Building a stress cone correctly takes time and patience, even with today's cold shrink 3M kits. Cutting corners is a recipe for disaster.
I would NEVER rely on a 5000 volt "megger" insulation tester simply because the cable is '4160'. You are in hi-pot land with shielded MV cable. A look at the Southwire DC hipot testing table will wake you up to MV cable testing.
http://www.southwire.com/support/DirectCurrentFieldTest.htm
There are strict guidelines and times involved to prove the stability of MV cables; rules that should not be taken lightly or omitted. Catastrophic cable failure is expensive in many respects beyond the actual cable loss. Loss of production can hurt a company very quickly.
Below are a couple more sites to help anyone understand what is needed to insure a safe, trouble free medium voltage installation. Anything less is simply a crapshoot.
http://www.generalcable.com/NR/rdonlyres/0129A307-6297-4D6A-B4A9-A21E527DE9A5/0/Spec_F025.pdf
http://www.chromausa.com/pdf/app-notes/AN-A Practical Guide to Dielectric Testing-092007.pdf
http://www.asresearch.com/events-training/pdfs/HotHipot.pdf
Again, if the the cable cleared after removing the stress relief, I would re-install another set of stress cones and hi-pot the cables again. It is by far the most economical method of repair. If your people are competent/ qualified to do hi-pot testing, then go for it. But if not, have professionals come in to do it. If it fails, you are only a grand or two into it. If it passes you are a hero.
And if everyone takes their time and does things right, no one will fool with those cables again until your retirement age. Then it won't be you anyway.
Mark