I think thats why Boeing went with 3 lifetimes on the 777 knowing what was coming down the road for WFD. The current FAR 25.571 Amnd 96 is what now requires a 2 lifetime fatigue test for new aircraft. With large OEM's,extended testing is definitely the way to go. Set the IOL at the 2 lifetimes then extend it to the full amount by justing taking advantage of the 3 lifetime testing which immediately gives you a 50% OEL extension.
Yeah the STC side is a bit more complicated. It is tough to do but not out of the question. We are currently working on 3 aircraft for which we are doing full up DTA and WFD assessments from scratch for the whole airplane. We have had to redevelop full external loads and internal loads as well as performing detailed stress analyses before even doing the DTA and WFD.
Obviously there can be considerable costs involved depending on the extent of the STC. Our efforts involve the full airframe. If however the STC was only on one component, ie fuselage, then the effort could be reduced significantly. Wings of course are probably the toughest due to all of the various additional loadings, from engines, gear, flight controls, and fuselage attachments involved. I've worked on several major STC mods such as cargo doors, large pods/antennas, and I can tell you its not as tough as doing the entire fuselage, wing and empennage. Actually its fairly straight forward once you have done it a few times. The key in all of this too is to have a large amount of fatigue test data. It doesnt necessary have to be for the exact aircraft so long as it is representative of the structural joints you are analyzing. Over the years I have accumulated well over a hundred reports on fatigue testing from coupons to large components and full scale fatigue tests. I can tell you that they have been invaluable and a great benefit to us in not only validating our analyses but also setting up our methods. Our entire SSF method for fatigue is based on alphas and betas established by test data.