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 <ref-law> 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.

Erwägungen:
1. Die II. sozialrechtliche Abteilung des Bundesgerichts ist zuständig zum Entscheid über die streitige Schadenersatzpflicht und zwar auch, soweit die Forderung entgangene Beiträge an die kantonale Familienausgleichskasse betrifft (Urteil 9C_901/2007 vom 8. Oktober 2008 E. 1, nicht publ. in: <ref-ruling>; 9C_704/2007 vom 17. März 2008 E. 1, nicht publ. in: <ref-ruling>, aber in SVR 2008 FL Nr. 1 S. 1).
2. Gemäss <ref-law> macht die zuständige Ausgleichskasse den Schadenersatzanspruch durch Verfügung geltend (Abs. 2). Der Schadenersatzanspruch verjährt zwei Jahre, nachdem die zuständige Ausgleichskasse vom Schaden Kenntnis erhalten hat, jedenfalls fünf Jahre nach Eintritt des Schadens. Diese Fristen können unterbrochen werden (Abs. 3 Satz 1 und 2). Wird der Schadenersatzanspruch aus einer strafbaren Handlung hergeleitet, für die das Strafrecht eine längere Verjährung vorschreibt, so gilt diese Frist (Abs. 4).
Bei den Fristen nach Art. 52 Abs. 3 und 4 AHVG handelt es sich um Verjährungsfristen, die unterbrochen werden können (<ref-ruling> E. 3.1 S. 427 mit Hinweis; BGE 9C_473/2008 vom 19. Dezember 2008 E. 4.1; Ueli Kieser, Alters- und Hinterlassenenversicherung, in: Ulrich Meyer [Hrsg.], SBVR/Soziale Sicherheit, 2. Aufl. 2007, S. 1308 Rz. 322; Marco Reichmuth, Die Haftung des Arbeitgebers und seiner Organe nach <ref-law>, 2008, S. 194 Rz. 813).
3. Streitig und zu prüfen ist, ob die Vorinstanz zu Recht erkannt hat, dass die Schadenersatzforderung gegenüber dem Beschwerdegegner verjährt sei. Dabei steht fest und ist unbestritten, dass die Verjährungsfristen des <ref-law> und nicht etwa längere strafrechtliche im Sinne von Abs. 4 derselben Bestimmung zur Anwendung gelangen, nachdem die gegen den Beschwerdegegner im Zusammenhang mit der konkursiten Firma unter anderem wegen Betrugs eingeleiteten Strafuntersuchungen am 15. Dezember 2006 eingestellt worden sind (Auskunft der Staatsanwaltschaft Y._ vom 13. August 2008).
3.1 Die Vorinstanz erwog, mit der Verfügung vom 18. August 2004 habe die Kasse die Verjährungsfrist vorerst gewahrt. Als einzigen den Lauf der Verjährung unterbrechenden Akt erwähnte sie den kantonalen Entscheid vom 28. Februar 2005 (der Kasse am 30. März zugestellt); hinsichtlich der Arbeitgeberkontrolle vom 13. Juni 2007 verneinte sie eine derartige Wirkung mit der Begründung, es handle sich nicht um eine "gerichtliche Handlung der Parteien" nach <ref-law>. Da die Kasse die Verfügung vom 2. (recte 6.) Dezember 2007 mehr als zwei Jahre nach der Eröffnung des kantonalen Entscheides erlassen habe, sei die Verjährungsfrist abgelaufen und die Schadenersatzforderung mithin verjährt.
3.2 Nach Auffassung der Ausgleichskasse ist die Verjährungsfrist auf jeden Fall eingehalten. Sie stellt sich auf den Standpunkt, diese sei mit der verfügungsweisen Geltendmachung des Schadenersatzbetrages am 18. August 2004 ein für allemal gewahrt worden. Ohnehin fände nicht die zweijährige Verjährungsfrist Anwendung, weil der Schaden zu den Zeitpunkten, welche die Vorinstanz als für die Auslösung bzw. Unterbrechung der Verjährungsfrist als massgebend betrachtet habe, nicht bekannt gewesen sei, habe doch das kantonale Gericht mit Entscheid vom 28. Februar 2005 die Sache zur Klärung der Schadenshöhe an die Kasse zurückgewiesen; massgebend sei die fünfjährige Frist, welche mit Eintritt des Schadens am 24. November 2003 (Ausstellung der Verlustscheine) zu laufen begonnen habe und in der Folge immer wieder rechtzeitig unterbrochen worden sei. Selbst wenn von der zweijährigen Verjährungsfrist auszugehen wäre, fände nach einer Unterbrechung einheitlich analog <ref-law> eine fünfjährige Frist Anwendung. In Bezug auf die möglichen Unterbrechungshandlungen sei zu berücksichtigen, dass über die in <ref-law> genannten Handlungen hinaus weitere Akte in Frage kämen. Auf jeden Fall hätten die Bemühungen der Kasse um Akteneinsicht und die Mitteilung der Einstellung des Strafverfahrens die Verjährungsfrist jeweils rechtzeitig unterbrochen. Mit Blick auf das Verbot rechtsmissbräuchlichen Verhaltens sei das fehlende Bemühen des Beschwerdegegners, bei der Schadensermittlung mitzuwirken, als Verjährungsverzicht zu werten.
3.3 Der Beschwerdegegner schliesst sich der Auffassung des kantonalen Gerichts an, wonach die Forderung verjährt sei. Er weist darauf hin, dass die Verwirkungsfristen des alten Rechts auf den 1. Januar 2003 in Verjährungsfristen umgewandelt worden seien. Die Ausführungen der Kasse, wonach die fünfjährige Verjährungsfrist Anwendung finde, seien konstruiert. Weshalb nach Unterbruch der zweijährigen Verjährungsfrist stets eine fünfjährige laufen solle, sei nicht nachvollziehbar. Unbehelflich seien auch die von der Beschwerdeführerin vorgebrachten Unterbrechungsgründe. Was schliesslich ihre Billigkeitsüberlegungen anbelange, übergehe die Kasse, dass er nie versucht habe, den Erlass der Schadenersatzverfügung hinauszuzögern, und sich nie geweigert habe, Unterlagen einzureichen oder Auskunft zu geben.
4. Geht es um die Haftung im Sinne von <ref-law>, stellt die Schadenersatzverfügung eine, in der Regel die erste verjährungsunterbrechende Handlung dar. Ergeht sie rechtzeitig innert der relativen zweijährigen Verjährungsfrist seit Kenntnis des Schadens, beginnt mit Erhebung einer Einsprache eine neue zweijährige Verjährungsfrist zu laufen (BGE 9C_473/2008 vom 19. Dezember 2008 E. 4.2.2). Entgegen der Auffassung der Ausgleichskasse wird mit der Schadenersatzverfügung die Verjährungsfrist indessen nicht "ein für allemal gewahrt", so dass "der seitherige Zeitverlauf [...] keinen Einfluss auf den Schadenersatzanspruch" mehr hätte. Dies entspräche der Rechtslage bei einer Verwirkungsfrist, wie sie vor der (auf den 1. Januar 2003 in Kraft gesetzten) Änderung des <ref-law> bestanden hat (vgl. dazu Urteil H 99/06 vom 11. September 2007 E. 5 mit Hinweis; ZAK 1991 S. 125, H 116/85 E. 2c; Thomas Nussbaumer, Das Schadenersatzverfahren nach <ref-law>, in: Schaffhauser/Kieser [Hrsg.], Aktuelle Fragen aus dem Beitragsrecht der AHV, 1998, S. 115).
Nach dem klaren Wortlaut von <ref-law> können aber die relative zweijährige und die absolute fünfjährige Verjährungsfrist unterbrochen werden. Dabei ist für die Beantwortung der damit zusammenhängenden Fragen, insbesondere welchen Handlungen der Ausgleichskasse und der Beschwerdeinstanzen verjährungsunterbrechende Wirkung zukommt, sinngemäss die Regelung für Forderungen aus unerlaubter Handlung (<ref-law> und <ref-law>) anwendbar. Der Schadenersatzanspruch nach <ref-law> kann somit auch während des Einspracheverfahrens oder verwaltungsgerichtlichen Beschwerdeverfahrens verjähren (BGE 9C_473/2008 vom 19. Dezember 2008 E. 4.2.2; Reichmuth, a.a.O., S. 214 Rz. 894f.).
Wird die Verjährung durch eine Klage oder Einrede unterbrochen, so beginnt im Verlaufe des Rechtsstreites mit jeder gerichtlichen Handlung der Parteien und mit jeder Verfügung oder Entscheidung des Richters die Verjährung von neuem (<ref-law>). Dabei entspricht die neue Verjährungsfrist der Dauer der unterbrochenen Frist (vgl. Ivo Schwander, in: Kren Kostkiewicz und andere, Handkommentar OR, 2002, N. 1 zu <ref-law>; Reichmuth, a.a.O., S. 213 Rz. 891). Für die von der Ausgleichskasse für richtig gehaltene Anwendung einer einheitlichen fünfjährigen Frist analog der die Veranlagungsverjährung regelnden Bestimmung des <ref-law> besteht mithin keine Handhabe.
5. 5.1 Die Beschwerdeführerin macht zu Unrecht geltend, weder zur Zeit der Zustellung der Pfändungsverlustscheine vom 24. November 2003 noch der ursprünglichen Schadenersatzverfügung am 18. August 2004 noch bei Zustellung des kantonalen Rückweisungsentscheides am 30. März 2005 - wie sich aus demselben ergebe - sei ihr der durch Beitragsverluste entstandene Schaden hinreichend bekannt gewesen; anwendbar sei deshalb nicht die zweijährige, ab Kenntnis des Schadens laufende, sondern die fünfjährige, mit Eintritt des Schadens in Gang gesetzte Verjährungsfrist. Denn nach der Rechtsprechung erlangt die Ausgleichskasse in dem Zeitpunkt Kenntnis vom Schaden, in welchem sie unter Beachtung der ihr zumutbaren Aufmerksamkeit erkennen muss, dass die tatsächlichen Gegebenheiten nicht mehr erlauben, die Beiträge einzufordern, wohl aber eine Schadenersatzpflicht begründen können (<ref-ruling> E. 2.1 S. 195, 128 V 15 E. 2a S. 17). Unabhängig davon, ob man mit der Vorinstanz als massgebenden Zeitpunkt die Zustellung der Pfändungsverlustscheine am 24. November 2003 bzw. hinsichtlich der Lohnsumme von Fr. 8'607.80 den Frühsommer 2004 oder mit dem Beschwerdegegner die Einstellung des Konkursverfahrens mangels Aktiven (im April 2004) betrachtet, ist die Schadenersatzverfügung rechtzeitig ergangen. Entgegen der Auffassung der Kasse kann jedenfalls aus dem Entscheid vom 28. Februar 2005, mit welchem die Sache an sie zurückgewiesen wurde zur Prüfung des von L._ vorgebrachten Einwandes, wonach dem Schadensbetrag zu hohe Lohnsummen zugrunde lägen, nicht abgeleitet werden, der Schaden sei ihr vor Durchführung der erforderlichen Abklärungen (Arbeitgeberschlusskontrolle etc.) noch gar nicht bekannt gewesen, reicht es doch rechtsprechungsgemäss, dass der Kasse die wesentlichen Merkmale des Schadens bekannt sind (vgl. <ref-ruling> E. 5a S. 12), was mit der Schadensermittlung aufgrund der Lohndeklarationen der Arbeitgeberin gewährleistet war.
5.2 Mit Erlass der Schadenersatzverfügung am 18. August 2004 hat die Kasse die laufende zweijährige Verjährungsfrist vorerst gewahrt. Im Verlaufe des Verfahrens folgten weitere die Verjährungsfrist unterbrechende Handlungen (<ref-law>), namentlich erging am 28. Februar 2005 der kantonale Rückweisungsentscheid, welcher der Kasse am 30. März 2005 zugestellt wurde. Mit Blick darauf, dass die von der Kasse gemäss diesem Entscheid zu erlassende Verfügung erst am 6. Dezember 2007 ergangen ist, stellt sich die Frage, ob der Fristenlauf in der Zwischenzeit erneut unterbrochen worden ist.
5.3 Aus den Akten ist ersichtlich, dass die Ausgleichskasse nach dem Rückweisungsentscheid vom 28. Februar 2005 mit Schreiben vom 11. März 2005 an den Mitverpflichteten L._ gelangt ist, um mit ihm eine Arbeitgeberkontrolle für den 3. Mai 2005 zu vereinbaren. Deren Durchführung scheiterte daran, dass die Akten nicht erhältlich gemacht werden konnten. Um an die dafür erforderlichen, von der Staatsanwaltschaft beschlagnahmten Buchhaltungsunterlagen der Firma X._ zu gelangen, hat die Kasse sich vorerst beim Konkursamt A._ (e-mail-Anfragen vom 11. und 29. September 2006), sodann bei der Kantonspolizei Zürich (Schreiben vom 6. Oktober 2006) und schliesslich bei der Abteilung Wirtschaftsdelikte der Staatsanwaltschaft des Kantons Zürich (Schreiben vom 25. Oktober 2006) nach denselben erkundigt und die angefragten Stellen darum ersucht, ihr Akteneinsicht zu gewähren. Anschliessend - am 13. Juni 2007 - hat sie eine Arbeitgeberkontrolle für die Zeit von Januar 2000 bis November 2003 durchgeführt.
5.4 Unter den Begriff "Verfügung oder Entscheidung des Richters" im Sinne von <ref-law> fallen (unter anderem) sowohl prozesserledigende Entscheide (Sach- oder Prozessentscheide) als auch prozessleitende Entscheide, sofern diese der Fortsetzung des Verfahrens dienen. Zu denken ist neben dem Erlass des Entscheides (vgl. auch BGE 24 II 205 E. 4 S. 211) etwa an Fristansetzungen an die Parteien (z.B. eine Editionsverfügung: BGE 21 246 E. 4 S. 251), Vorladungen zu gerichtlichen Verhandlungen oder die Durchführung von Beweis- und Hauptverhandlungen, die Sistierung des Prozesses (<ref-ruling> E. 1 S. 433, 123 III 213 E. 3 S. 216), die Gewährung der aufschiebenden Wirkung (<ref-ruling> E. 4b S. 61 f.). Nicht erforderlich ist, dass die Verfügungen oder Entscheidungen formell in Verfügungs- oder Entscheidform gekleidet sind (Urteil B 87/00 vom 10. Februar 2004 E. 1.4.2; Stephen V. Berti, Zürcher Kommentar, 3. Aufl., N. 24 zu <ref-law>; Robert K. Däppen, Basler Kommentar, 4. Aufl., N. 3 zu <ref-law>). In diesem Sinne hat das Bundesgericht Erkundigungen des kantonalen Instruktionsrichters nach dem Stand der dort hängigen staatsrechtlichen Beschwerde betreffend Ablehnung der unentgeltlichen Rechtspflege im kantonalen Verfahren (<ref-ruling> E. 4 und 4b S. 61 f.), den Abschluss des Schriftenwechsels durch Zustellung der Berufungsantwort und der Vernehmlassung zur staatsrechtlichen Beschwerde (<ref-ruling> E. 6b S. 220) und der Aufforderung an die Pensionskasse, ihr Reglement einzureichen (Urteil B 87/00 vom 10. Februar 2004 E. 1.5), verjährungsunterbrechende Wirkung beigemessen. Demgegenüber unterbrechen rein interne Handlungen eines Gerichts, selbst wenn sie Verfügungscharakter haben (wie beispielsweise die Ernennung des Referenten, die Anordnung der Aktenzirkulation, das Erstellen von Auszügen aus den Akten), die Verjährung nicht, ausser sie würden den Parteien eröffnet (<ref-ruling> E. 6b S. 220; vgl. auch Pascal Pichonnaz, Commentaire romand, N. 6 zu <ref-law>; Spiro, Die Begrenzung privater Rechte durch Verjährungs-, Verwirkungs- und Fatalfristen, 1975, Bd. I, S. 348 Fn. 28). Ebenfalls nicht als Verfügung des Richters im Sinne von <ref-law> anerkannt wurden die Erkundigungen des Zivilrichters nach dem Stand eines Strafverfahrens (BGE 75 II 227 E. 3a S. 232). Keine verjährungsunterbrechende Wirkung kommt sodann den gerichtlichen Handlungen zu, die aus Anlass des Verfahrens vorgenommen werden, jedoch nicht unmittelbar auf dessen Fortgang bzw. Erledigung gerichtet sind, wie etwa die Ausfällung einer Ordnungsstrafe und ein darauf bezogenes Beschwerdeverfahren (BGE 21 246 E. 4 S. 251).
5.5 Bei den (mittels e-mail und mittels per Post versandten Schreiben erfolgten) Erkundigungen der Ausgleichskasse nach dem Verbleib der beschlagnahmten Akten handelt es sich, da die Kasse dabei an andere Verwaltungsstellen (das Konkursamt, die Polizei und die Staatsanwaltschaft) gelangt ist, nicht um rein interne Handlungen, welchen praxisgemäss - jedenfalls soweit sie den Parteien nicht eröffnet wurden - keine verjährungsunterbrechende Wirkung zukommt. Allerdings hat die Kasse die Akten - anders als das Gericht im Verfahren B 87/00 (Urteil vom 10. Februar 2004) - auch nicht bei einer am Recht stehenden Partei erhältlich zu machen versucht, weshalb parteiseits von den entsprechenden Handlungen gar keine Kenntnis erlangt wurde. Gerade dies wäre aber - auch im Sinne der ratio legis - für die Zuerkennung verjährungsunterbrechender Wirkung entscheidend (vgl. <ref-ruling> E. 2.3.1 S. 679, 130 III 202 E. 3.2 S. 207, 106 II 32 E. 4 S. 35 f. [betreffend gerichtliche Handlungen der Parteien]). Die Bemühungen der Kasse sind hinsichtlich der Bestimmung des <ref-law> gleich zu qualifizieren wie die in BGE 75 II 227 E. 3a S. 232 beurteilte Nachfrage des Zivilrichters nach dem Stand eines Strafverfahrens; auch sie unterbrechen den Lauf der Verjährungsfrist mithin nicht. Da die Verjährungsfrist somit bereits bei Durchführung der Arbeitgeberschlusskontrolle am 13. Juni 2007 abgelaufen war, braucht deren Wirkung auf den Fristenlauf nicht erörtert zu werden.
5.6 Nicht gefolgt werden kann der Ausgleichskasse schliesslich auch, soweit sie unter Bezugnahme auf das Rechtsmissbrauchsverbot geltend macht, der Beschwerdegegner habe seine Mitwirkungspflicht bei der Erhebung der Lohngrundlagen nicht wahrgenommen, welches Verhalten ihm als Verjährungsverzicht anzurechnen sei. Denn als rechtsmissbräuchlich im Sinne von <ref-law> nicht zu schützen wäre die Einrede der Verjährung nur, wenn sie gegen erwecktes Vertrauen verstossen würde, der Schuldner insbesondere ein Verhalten gezeigt hätte, das den Gläubiger bewogen hätte, während der Verjährungsfrist rechtliche Schritte zu unterlassen, und das seine Säumnis auch bei objektiver Betrachtungsweise als verständlich erscheinen liesse (<ref-ruling> E. 2 S. 437). Indessen ist nicht ersichtlich und wird auch von der Kasse nicht dargetan, mit welchem Verhalten der Beschwerdegegner bei ihr berechtigtes Vertrauen erweckt haben könnte. Dass die Verwaltung nicht rechtzeitig rechtliche Schritte gegenüber dem Beschwerdegegner unternommen hat, kann diesem nicht angelastet werden.
5.7 Bei dieser Sachlage ist der Schadenersatzanspruch gegenüber dem Beschwerdegegner verjährt, wie die Vorinstanz zu Recht erkannt hat.
6. Das Verfahren ist kostenpflichtig. Die Ausgleichskasse hat als unterliegende Partei die Gerichtskosten zu tragen (<ref-law>). Dem Beschwerdegegner steht bei diesem Prozessausgang eine Parteientschädigung zu (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Die Gerichtskosten von Fr. 5000.- werden der Beschwerdeführerin auferlegt.
3. Die Beschwerdeführerin hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 3000.- zu entschädigen.
4. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich, dem Bundesamt für Sozialversicherungen, L._ und S._ schriftlich mitgeteilt.
Luzern, 21. Januar 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Meyer
Die Gerichtsschreiberin: Keel Baumann