Keyword-stuffing was a day one phenomenon as soon as search engines decided to rank pages according to keyword weights in meta tags.
Lycos, for example, only supported the meta tag for a few months and then dropped it in, what 98?, because it led to irrelevant results.
AltaVista was one of the last engines to drop support and that was IIRC the core reason why its results were useless.