The one elephant that jumps to mind is liquidity. The mechanisms by which liquidity in the markets affect the end results are absolutely key to how your algorithm's interactions with the data will pan out. With that in mind, the methods by which we come by liquidity have dramatically transformed over the years, and market makers from >10 years ago operated in an entirely different way. That's my $0.02, anyhow.
Anecdotal evidence: I have first-hard experience implementing algorithms that chugged along just fine with 10 years of data for backtesting.
You could ask the same question about many different regulatory changes, but Reg NMS is likely to be the biggest.
In any case, I believe the scarcity the parent was referring to was for the fundamental data, i.e. earnings, value/share, dividend yields, cash on hand, etc. This data is harder to come by compared to the standard open-high-low-close pricing data, which is what most algorithms use (although not necessarily the best algorithms ;-)