It is actually quite easy to explain why it happened so late and it was a curious instance of coincidence.
After the war many Nazis remained unscathed, the "denazification" program was effectively as successful as trying to drink out an ocean with a teaspoon. While only a minority of Germans were dedicated nazis, many of them had acquired power positions under Nazi Germany, lying is easy and suitable replacement was hard to get by (remember: many political opponents were killed, too). So many of them collaborated with the Western Allies, having a deep resentment against Russia and the former Germans were very silent about what has been done. East Germany was under Russian control and many socialist people who survived were emigrating to it, e.g. Bertholt Brecht.
It could have been going the normal way by forgetting, suppressing and denying or aggressively attacking, business as usual. In fact there were many instances when it was evident that the old system had still its followers. Citing from German wikipedia, in spring 1957 Ludwig Zind insulted a Jewish businessman and admitted to have killed hundreds of Jews, he was charged with insult and Verunglimpfung des Andenkens Verstorbener (denigration of the dead) and convicted for one year. He openly admitted being a Nazi and got approval from the spectators, but fled before incarceration.
In the same year Friedrich Nieland from Hamburg was disseminating nazi propaganda, but was not convicted before the Oberlandesgericht Hamburg.
The former concentration camp doctor Hans Eisele also fled from Germany, another female doctor, Herta Oberheuser, was discharged from prison and could work again as doctor.
January 1959 the government tried to change the Volksverhetzung (incitement) paragraph, § 130 StGB after further justice scandals and arson attacks against synagogues. Those arson attacks reached a sad peak at the end of 1959, the most notable case the synagogue in Cologne.
But then the 1968s happened; the next generation was growing up and was very critical over the perceived values of the war generation, especially because they were thought responsible for the war. As German I know from own experience (I worked as alternative civilian service a short time) that many Germans living during the Nazi period were extremely silent about what they were doing during this time. I also know that many other people who were young in this period shared exactly the same sentiment: Something was very wrong and their parents was hiding something.
The people now were already critizing the Holocaust and in the 70s there was a strengthened activity of denial literature, but it was all overshadowed by the clash of left terrorism (RAF) and the government in the 70s. This era was ending at the end of 1977 when the core RAF died in the high security prison Stammheim.
What now happened was the sending of the TV series Holocaust - Die Geschichte der Familie Weiss during the year 1979. It was extremely popular in Germany and brought an overdue widespread discussion. It triggered a ferious propaganda counterattack of the German Nazis with denials and denunciations and at the first time they realized that their worldview was losing more and more to be an acceptable position.. This urged them to give their writings a "scientific" or "asking open question" touch.
Being flooded with propaganda, justice minister Hans A. Erhard tried to introduce 1985 the revision of the §130 which was delayed, but he was successful to introduce a passage for insult § 194.
§194 StGB Beleidigung (insult) was changed so that claiming publicly that a person who died as victim of a nazi crime was not killed was sufficient to bring it forward to a judge even if it was not reported, only the insulted person could stop the process. It was introduced in August 1st, 1985
§130 StGB Volksverhetzung (incitement) got a new passage (3) at December 1st, 1994
So essentially the real or perceived tenacity of the Holocaust deniers triggered the introduction of the law. It must be said that many people and jurists are also uncomfortable with this law because it gives judges too much leeway in the persecution of persons.