From my recalling, a few years at most. There was, and apparently still exists, distributed.net which was aimed at brute forcing DES (easy), RC5-56 bits and then RC5-64 bits by establishing a web of personal computers (via a client one had to install). Thus it was well known brute forcing was achievable in a reasonable time.

PGP (1991) was considered secure as it was considered not brute forceable. With 128 bits, it was considered military grade at the time and the US had an export restriction due to that. That might have been an incentive for GNU Privacy Guard. In France you had to give your private key to the government authority if an encryption system used anymore than 56 bits (as I recall, I don't remember the exact number).

In 1999, factoring RSA-512 required roughly 292 CPU-years of work distributed across hundreds of academic machines, running for about 7 months. The community already knew it was weak -- the US export restrictions on 512-bit RSA were explicitly calibrated so the NSA could break it while casual adversaries couldn't.

Consumer hardware doing it in a couple of days in 2025 is roughly in line with Moore's Law extrapolations people were drawing at the time. The surprise isn't really the timeline. It's that someone did it as a weekend project rather than a nation-state effort.