512 bits (rounded down from the 664 bits or 200 digits in the patent) was recommended from its conception in 1974 and throughout the 1980s. Indeed, 463 bits was considered sufficient in the mid-1990s for the RSA-140 challenge. Whether key strengths as low as 100 digits (330 bits) were ever used in the early 1980s embedded systems is unclear; but probable given the RSA-100 challenge of 1991.
RSA's recommended key size increased to 768 (user) or 1024 (enterprise) at some point in the late 1990s1 due to academic successes in breaking bit strengths leading up to 512 bits.
Current recommendations (SP 800-572) are now 2048 or 3072 bits, depending on interoperability requirements.
In practice, these key strengths do not smoothly match Moore's Law as each new key size requires overhauling embedded systems and resolving interoperability requirements. So the trend has been to pick a key size much larger than necessary until the risk of breaching occurs, then pick another key size much larger than necessary.
A coarse stepwise increase governed by infrastructure costs and collective public perception of key strength.
1. Inferred from this RSA article and this (irritatingly uncited) Wikipedia section.
2. A sister document of the PDF cited in the question.