Like OS, I started out in the 60s (maybe a year or two ahead of his goodself) when much of the heavy performance changes were in the making ... and we both are probably looking more toward fishing rather than aeroplanes in the next few years or so ... unfortunately, we probably don't have the old school Aus regulatory folk, such as IST and JCF in the PPRuNe community .. they would be able to quote chapter and verse of the whole developmental lineage as if it were only yesterday ... (if it sounds like I was in a bit of awe of those folk .. then that would be a fair assessment ..)
The earlier certification standard at the time (CAR4b) was a bit like an upmarket FAR23 package for performance and required a level of OEI capability .. if you really want to be adventurous, have a looksee
here.
During the mid to late 60s, ICAO put out a PAMC (Provisional Acceptable Means of Compliance) on aircraft performance (looking at some notes tucked away in the computer archives .. I think Circular 58-AN/53/2 ?) .. I have a copy in a filing cabinet somewhere but wouldn't like to have to find it in a hurry ... normal sort of doc .. around the 30-40 page size, as I recall ? .. long time since I've looked at it ...
The F27, if I recall correctly, probably was the first turbine powered aircraft to recertify from the older to the newer standards eventually embodied in FAR25 (which came on the scene in the mid-60s).
The Industry then saw the now "normal" OEI segmented takeoff capabilities evolve into a more general application in the general heavy aircraft sandpit ...
As for the problems associated with getting obstacle data .. while it is getting easier with satellite imagery ... the bulk of the work done Industry wide is geared to the initial takeoff ... with the majority tending to ignore what happens between then and LSA ... folk like Mutt, OS, and me worry about that latter bit a lot as satisfying it takes the most detective effort in finding out just what rocky bits exist for a given departure .. Centaurus, for one, could regale us with tales of operators who tend even not to worry about the early rocky bits .. but that is another tale for another day ...
Generally, if you are still struggling at 25nm, then you are having a bad day .. the real problem, then, is with those aerodromes which have a high MSA.