I first heard about this as a kid in 1999. I didn't even have internet back then (only got it in year 2000), and my country had just been bombed by NATO (your regular bombing campaign sprinkled with bombing civilians, as is tradition) and was lead by Slobodan fucking Milošević (a colossal piece of shit), so all kinds of conspiracies were flying around, everything was disinformation, and I didn't put much weight on this story even though my parents discussed it with friends several times during the next decade, which is why I remember it.
My parents' friend who had lived in New Zealand for a decade at that point came to the country to bury his father and was over at our house for dinner. He's an electrical engineer and used to work for a telco in New Zealand. He had heard about this ECHELON thing from multiple colleagues and found it plausible enough to talk about. He was told that all internet and phone traffic was being recorded realtime. Mind you, this was pre-9/11, so no 'terrorist threats'. The world ran on shitty computers and expensive storage and voice in any form (even compressed telephony) was considered bulky at the time. And this is 15 years prior to the machine learning boom, voice transcription was really bad, I still doubt it was used at that point, even though he mentioned it.
But he had witnessed an expansion of fiber and datacenter capacity sometime in 1997-99 and it seemed plausible to him (a real serious and professional guy).
Imagine my surprise when it turned out to be true. I mean, the story slowly became less and less far fetched over the following decade, but was still a total surprise when Snowden blew the whistle.