Sachverhalt: A. A.a Am ... November 2003 wurde über die Firma X._ der Konkurs eröffnet. In diesem Verfahren (welches vorerst am ... April 2004 mangels Aktiven eingestellt, aber dann im Sinne von Art. 230 Abs. 2 SchKG fortgesetzt worden war) kam die Ausgleichskasse des Kantons Zürich mit einer Forderung aus bundes- und kantonalrechtlichen Sozialversicherungsbeiträgen und Nebenkosten in der Höhe von Fr. 136'934.40 zu Verlust. Mit Verfügungen vom 18. August 2004 forderte sie von H._, L._ und S._, ehemalige Verwaltungsräte der konkursiten Firma, in solidarischer Haftung Schadenersatz in der Höhe von Fr. 136'934.30. Die von denselben erhobenen Einsprachen hiess die Kasse teilweise gut; dabei setzte sie die Schadenersatzforderung gegenüber H._ auf Fr. 135'492.25, gegenüber L._ auf Fr. 121'965.55 und gegenüber S._ auf Fr. 130'990.15 herab (Einspracheentscheide vom 25. Oktober 2004). Die dagegen erhobenen Beschwerden hiess das Sozialversicherungsgericht des Kantons Zürich am 28. Februar 2005 in dem Sinne gut, dass es die angefochtenen Einspracheentscheide aufhob und die Sache zur Abklärung im Sinne der Erwägungen sowie neuer Verfügung an die Kasse zurückwies. A.b In Nachachtung dieses kantonalen Entscheides liess die Kasse am 13. Juni 2007 eine Arbeitgeberkontrolle (für die Zeit von Januar 2000 bis November 2003) durchführen. Gestützt darauf forderte sie mit Verfügungen vom 6. Dezember 2007 von H._, L._ und S._ in solidarischer Haftung erneut Schadenersatz von Fr. 136'934.30. Betreffend L._ und S._ erwuchsen die Verfügungen in Rechtskraft. Die von H._ erhobene Einsprache hiess die Kasse in dem Sinne teilweise gut, als sie die Schadenersatzforderung auf Fr. 135'492.25 reduzierte (Einspracheentscheid vom 25. April 2008). B. Beschwerdeweise liess H._ das Rechtsbegehren stellen, der Einspracheentscheid sei ersatzlos aufzuheben. In prozessualer Hinsicht beantragte er, es sei vorerst über die geltend gemachte Einrede der Verjährung zu befinden. Mit Entscheid vom 29. August 2008 hiess das Sozialversicherungsgericht des Kantons Zürich die Beschwerde gut, hob den angefochtenen Einspracheentscheid vom 25. April 2008 auf und sprach H._ eine Parteientschädigung zu Lasten der Ausgleichskasse zu. C. Die Ausgleichskasse des Kantons Zürich lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Rechtsbegehren, der kantonale Entscheid sei aufzuheben. Eventualiter sei die Sache an die Vorinstanz zurückzuweisen, damit diese die Begründetheit des Schadenersatzanspruchs, wie er mit Einspracheentscheid vom 25. April 2008 festgestellt wurde, in seinen Voraussetzungen prüfe. H._ lässt auf Abweisung der Beschwerde schliessen. Das Bundesamt für Sozialversicherungen verzichtet auf eine Vernehmlassung.