Sachverhalt:
A.
Mit Einspracheentscheid vom 3. Mai 2012 verpflichtete die Ausgleichskasse des Kantons Zürich A.A._ und B.A._, ihr in solidarischer Haftung Schadenersatz im Betrag von Fr. 73'157.60 für entgangene Sozialversicherungsbeiträge zu entrichten. Die vom 4. Mai 2012 datierende Sendung (Poststempel), adressiert an Rechtsanwalt C._, der A.A._ und B.A._ seit dem 23. Juli 2007 in dieser Sache vertreten hatte, wurde mit dem Vermerk "weggezogen, Nachsendefrist abgelaufen" retourniert. In der Folge verschickte die Ausgleichskasse den Entscheid direkt an A.A._ und B.A._, welcher mit dem Hinweis auf bis ca. 31. August dauernde Ferienabwesenheit wiederum retourniert wurde. Am 30. August 2012 sandte die Ausgleichskasse den Einspracheentscheid A.A._ und B.A._ erneut eingeschrieben zu unter Hinweis auf die erfolglosen Zustellversuche.
B.
Auf eine dagegen erhobene Beschwerde trat das Sozialversicherungsgericht des Kantons Zürich mit Beschluss vom 22. Dezember 2012 nicht ein. In Gutheissung der hiegegen erhobenen Beschwerde hob das Bundesgericht mit Urteil 9C_214/2013 vom 31. August 2013 den angefochtenen Entscheid auf und wies die Sache zur Gewährung des Replikrechts und zur Neubeurteilung an die Vorinstanz zurück.
C.
Das Sozialversicherungsgericht des Kantons Zürich führte einen zweiten Schriftenwechsel durch und trat mit Beschluss vom 31. August 2015 wiederum nicht auf die Beschwerde ein.
D.
A.A._ und B.A._ führen Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, der angefochtene Beschluss sei aufzuheben und die Sache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem sei der Beschwerde die aufschiebende Wirkung zu erteilen.
Während die Beschwerdegegnerin auf Abweisung der Beschwerde schliesst, lässt sich das Bundesamt für Sozialversicherungen nicht vernehmen.

Erwägungen:
1.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten kann u.a. die Verletzung von Bundesrecht gerügt werden (<ref-law>), die Feststellung des Sachverhalts nur, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 beruht (<ref-law>).
2.
Zunächst rügen die Beschwerdeführer, das kantonale Gericht habe Art. 6 Ziff. 1 EMRK bzw. <ref-law> verletzt, indem es ihnen die Stellungnahme der Verwaltung (Duplik) vom 19. März 2014 erst am 17. Oktober 2015 zugestellt habe, mithin rund eineinhalb Monate nach Fällung des angefochtenen Entscheids. Damit habe die Vorinstanz die Wahrnehmung des Replikrechts abermals verunmöglicht.
2.1. Gemäss Art. 29 Abs. 1 und 2 BV und Art. 6 EMRK haben die Parteien eines Gerichtsverfahrens einen unbedingten Anspruch darauf, zu sämtlichen Eingaben der Gegenpartei Stellung zu nehmen, falls sie dies wünschen (sog. unbedingtes Replikrecht: <ref-ruling> E. 3.2 S. 191 f.; <ref-ruling> E. 2.3.3 S. 157 und 484 E. 2.1 S. 485; <ref-ruling> E. 2.3.1 S. 197; <ref-ruling> E. 4.3-4.7 S. 102 ff.). Die Parteien haben somit einen verfassungsmässigen Anspruch darauf, sich zu jeder Eingabe im Verfahren zu äussern, unabhängig davon, ob sie neue oder wesentliche Vorbringen enthält. Das Gericht muss vor Erlass seines Urteils eingegangene Vernehmlassungen den Beteiligten zustellen, damit diese sich darüber schlüssig werden können, ob sie sich dazu äussern wollen oder nicht (BGE <ref-ruling> E. 2.3.1 S. 197).
2.2. In sachverhaltlicher Hinsicht stellte die Vorinstanz fest, die Duplik vom 19. März 2014 sei den Beschwerdeführern am 11. Mai 2015 zur Kenntnis gebracht worden, was von diesen bestritten wird. Gemäss den Verfahrensakten wurde die Duplik mit Mitteilung vom 11. Mai 2015 an den Rechtsvertreter der Beschwerdeführer versandt, wobei der Versand offensichtlich - weder ist auf der Mitteilung ein Vermerk auf ein Einschreiben bzw. eine Gerichtsurkunde angebracht noch findet sich ein Track&Trace-Auszug bzw. Empfangsschein für Gerichtsurkunden in den Akten - mit normaler Post erfolgte. Wird - wie vorliegend - die Tatsache (wie auch das Datum) der Zustellung uneingeschriebener Sendungen bestritten, muss, da der Beweis für die Zustellung in concreto auch nicht anderweitig erbracht wird, im Zweifel auf die Darstellung des Empfängers abgestellt werden (<ref-ruling> E. 2.2 S. 10 und 124 V 400 E. 2a S. 402; Urteile 9C_830/2015 vom 6. April 2016 E. 5.3.2; 9C_282/2014 vom 25. März 2015 E. 3.2). Die hievon abweichende Feststellung des kantonalen Gerichts ist, da sie diese Beweisregel verletzt, für das Bundesgericht nicht verbindlich (E. 1 hievor). Daher ist festzuhalten, dass die Duplik dem Rechtsvertreter der Beschwerdeführer am 17. Oktober 2015 und damit erst nach Erlass des angefochtenen Entscheids zugestellt wurde.
Trotz der hievor dargelegten Ausgangslage geht die Berufung auf eine Verletzung des Replikrechts in concreto fehl. Die Grundrechte müssen - wie auch der EGMR stets betont - nicht theoretisch und abstrakt, sondern konkret und effektiv geschützt werden (BGE <ref-ruling> E. 2.8 S. 159 f. mit Hinweis auf das Urteil des EGMR Schlumpf gegen Schweiz vom 8. Januar 2009 [29002/06], § 57, mit weiteren Hinweisen). Das Recht auf Kenntnisnahme von und Stellungnahme zu Eingaben der übrigen Verfahrensbeteiligten dient dem fairen Verfahren in dem Sinne, dass die Verfahrensparteien die Möglichkeit haben, sich substanziell zu Vorbringen der Gegenpartei zu äussern. Das blosse Beharren darauf, das letzte Wort zu haben, ohne dass damit eine effektive Rechtswahrnehmung verbunden wäre, ist demgegenüber nicht schutzwürdig (BGE a.a.O. E. 2.8 S. 160 mit Hinweis). In casu wird weder hinreichend geltend gemacht noch ist (anderweitig) ersichtlich, welche rechtserheblichen Umstände die Beschwerdeführer - auf die wenige Zeilen umfassende Duplik hin, welche sich in der Bestätigung der bereits gestellten Anträge und im Verweis auf die Verfügungen bzw. Eingaben der Verwaltung sowie die bereits aufgelegten Akten erschöpft - denn noch hätten vorbringen wollen oder können: Soweit vorgebracht wird, der Umstand hätte Anlass "zu einigen Bemerkungen" gegeben, dass die Verwaltung nichts zur Zustellfiktion und zu "ihrer nicht besonders professionellen Arbeitsweise" ausgeführt habe, kann darin schlechterdings kein rechtserheblicher Umstand erblickt werden. Dasselbe gilt für den Einwand, durch den Verweis auf den Einspracheentscheid bzw. ihre Vernehmlassung habe die Verwaltung "nochmals sämtliche Argumente" vorgebracht und zu diesen hätten sich die Beschwerdeführer nochmals äussern wollen. Dies nota bene nachdem die Beschwerdeführer zu den Argumenten der Verwaltung bereits mit einer umfangreichen (32-seitigen) Replik Stellung genommen hatten. Unter diesen Umständen, und anders als noch im Verfahren 9C_241/2013, erscheint die Berufung auf das Replikrecht - welches vorliegend zur leeren Formalität verkommt, die keinen Rechtsschutz verdient - rechtsmissbräuchlich (vgl. in <ref-ruling> nicht publ. E. 4.3.2 des Urteils 2C_978/2012, 2C_979/2012 vom 4. Mai 2013; Urteil 5A_825/2012 vom 17. April 2013 E. 3.3). Offenbleiben kann nach dem Gesagten die Frage, ob das Verhalten der Beschwerdeführer gleichzeitig auf blosse Verzögerung des seit Juni 2007 hängigen Schadenersatzverfahrens ausgerichtet ist.
3.
Die Beschwerdeführer hatten im vorinstanzlichen Verfahren die Durchführung einer öffentlichen mündlichen Verhandlung verlangt. Weil ihrem Antrag nicht entsprochen worden ist, sehen sie nun Art. 6 Ziff. 1 EMRK verletzt.
3.1. Gemäss Art. 6 Ziff. 1 EMRK hat jedermann u.a. Anspruch darauf, dass seine Sache öffentlich von einem Gericht gehört wird, das über zivilrechtliche Ansprüche und Verpflichtungen oder über die Stichhaltigkeit einer strafrechtlichen Anklage zu entscheiden hat. Nach der Rechtsprechung hat das kantonale Gericht, welchem es primär obliegt, die Öffentlichkeit der Verhandlung zu gewährleisten, bei Vorliegen eines klaren und unmissverständlichen Parteiantrages grundsätzlich eine öffentliche Verhandlung durchzuführen (<ref-ruling> E. 3 S. 54). Ein während des ordentlichen Schriftenwechsels gestellter Antrag gilt als rechtzeitig (<ref-ruling>).
3.2. Das kantonale Gericht ging von einem verspäteten Antrag aus und erachtete die Durchführung der anbegehrten Verhandlung überdies als entbehrlich, weil die Eintretensvoraussetzungen nicht erfüllt seien, mithin der Entscheid auf ein Nichteintreten lauten werde und solche verfahrensrechtliche Entscheidungen nicht unter Art. 6 EMRK fielen (<ref-ruling> E. 3b/dd S. 56). Hiegegen wenden die Beschwerdeführer ein, auf eine Verhandlung könne nur verzichtet werden, wenn die Unzulässigkeit der Beschwerde offensichtlich sei, welches Kriterium hier nicht erfüllt sei.
Der Einwand der Beschwerdeführer ist unbegründet. Zwar trifft zu, dass der kantonale Richter von einer ausdrücklich beantragten Verhandlung nur absehen kann, wenn sich auch ohne öffentliche Verhandlung mit hinreichender Zuverlässigkeit erkennen lässt, dass eine Beschwerde offensichtlich unbegründet oder unzulässig ist, namentlich wenn formelle Eintretensvoraussetzungen nicht erfüllt sind, etwa weil die Rechtsmittelfrist eindeutig versäumt wurde oder wenn die Rechtsschrift allfälligen unabdingbaren Formerfordernissen nicht genügt (<ref-ruling> E. 1 S. 281 mit Hinweis auf <ref-ruling> E. 3b/dd S. 56). Ein solcher Fall liegt - wie nachfolgend zu zeigen ist (E. 4 hiernach) - entgegen der Beschwerde jedoch vor. Damit hält der Verzicht auf eine Verhandlung nach Art. 6 Ziff. 1 EMRK vor Bundesrecht stand, ohne dass die - ebenfalls umstrittene - Frage der Rechtzeitigkeit des Antrags geprüft werden muss.
4.
4.1. Zur Frage der Rechtzeitigkeit der Beschwerde an das kantonale Versicherungsgericht erwog die Vorinstanz im Wesentlichen, der damalige Rechtsvertreter der Beschwerdeführer habe es unterlassen, der Verwaltung Meldung über seine - nach Einsprache vom 8. November 2010 erfolgte - Adressänderung zu machen. Damit habe er seine Melde- und Informationspflichten (Art. 12 des Bundesgesetzes über die Freizügigkeit der Anwältinnen und Anwälte vom 23. Juni 2000 [BGFA; SR 935.61]) verletzt. Daran würde nichts ändern, wenn er - gemäss Vorbringen der Beschwerdeführer - einen auf ein Jahr befristeten Nachsendeauftrag bei der Post eingerichtet und mit den Anwälten an der ursprünglichen Adresse intern eine Weiterleitung der für ihn allenfalls eingehenden Post vereinbart hätte. Diese Unterlassung des Rechtsanwalts hätten sich die Beschwerdeführer anrechnen zu lassen. Somit gelte der Einspracheentscheid vom 3. Mai 2012 aufgrund der Zustellfiktion in jedem Fall spätestens Mitte Mai 2012 als zugestellt. Die beschwerdeführerischen Einwände seien unbegründet: Der Schluss auf eine fehlerhafte Zustellung durch die Post sei haltlos, sei die Retournierung der Sendung doch auf das Verschulden des damaligen Rechtsvertreters zurückzuführen. Ferner habe die direkte Zustellung an die Beschwerdeführer keine neue Frist ausgelöst. Schliesslich seien die Voraussetzungen für eine Wiederherstellung der Frist gemäss <ref-law> nicht gegeben, weil die Postsendung vom 4. Mai 2012 wie dargelegt infolge Verschuldens des damaligen Rechtsanwalts nicht erfolgreich habe zustellt werden können.
Die Beschwerdeführer rügen, indem die Vorinstanz dem damaligen Rechtsvertreter die fehlerhafte Zustellung angelastet habe, habe sie Bundesrecht verletzt. Namentlich habe der Rechtsvertreter, nachdem die Verwaltung über eineinhalb Jahre untätig geblieben sei, schlechterdings nicht mehr mit einer Zustellung rechnen müssen, womit auch die Pflicht zur Adressänderung entfallen sei. Es gehe deutlich zu weit, wenn die Vorinstanz vom Rechtsbeistand nach Ablauf der Frist für die Zustellfiktion weitere Vorkehrungen erwarte.
4.2. Zunächst ist festzuhalten, dass der beschwerdeweise angerufenen Rechtsprechung, wonach bei einem Zeitraum von über einem Jahr seit dem letzten Kontakt mit der Behörde nur noch eine Empfangspflicht des am Verfahren Beteiligten besteht, eine Beschwerde einer nicht vertretenen Privatperson zugrunde lag (Urteil 2C_1040/2012, 2C_1041/2012 vom 21. März 2013 E. 4.1, in: StE 2013 B 93.6 N. 33 mit Hinweis). Damit erscheint äusserst fraglich, ob diese Rechtsprechung auch auf die im Verwaltungsverfahren professionell vertretenen Beschwerdeführer zur Anwendung gelangt. Doch ungeachtet dessen, ob in casu die Zustellfiktion (<ref-law>) anwendbar ist oder ob angesichts der knapp 19-monatigen Frist zwischen der letzten verfahrensbezogenen Handlung der Verwaltung und dem Einspracheentscheid bloss eine Empfangspflicht besteht, war der damalige Rechtsvertreter in jedem Fall verpflichtet, dafür zu sorgen, dass ihm behördliche Akte zugestellt werden können. Dies bedingt, dass den Behörden eine Adressänderung bekannt gegeben wird (erwähntes Urteil 2C_1040/2012, 2C_1041/2012 E. 4.1; Urteil 9C_102/2016 vom 21. März 2016 E. 2; <ref-ruling> E. 4b/aa S. 94; vgl. auch WALTER FELLMANN, in: Fellmann/Zindel [Hrsg.], Kommentar zum Anwaltsgesetz, 2011, N. 17 zu <ref-law>; KASPAR SCHILLER, Schweizerisches Anwaltsrecht, 2009, Rz. 1637). Die Mitteilung seiner neuen Adresse an die Verwaltung hat der damalige Rechtsvertreter nach den verbindlichen (E. 1 hievor) und im Übrigen unbestritten gebliebenen Feststellungen der Vorinstanz jedoch unterlassen. Dass er andere diesbezügliche Vorkehren getroffen habe, ändert daran nichts, waren diese doch offensichtlich nicht geeignet, eine erfolgreiche Zustellung des Einspracheentscheids zu gewährleisten. Auch ist evident, dass ein befristeter Nachsendeauftrag der Post die Bekanntgabe der neuen Adresse nicht zu ersetzen vermag. Mithin ist der vorinstanzliche Schluss, der damalige Rechtsvertreter habe seine Pflichten im Zusammenhang mit seiner Adressänderung verletzt und dadurch die Zustellung des Einspracheentscheids vereitelt, was sich die Beschwerdeführer anzurechnen hätten, bundesrechtskonform.
Kann eine Zustellung an die bekannt gegebene Adresse nicht erfolgen, weil die Angabe einer aktuellen Adresse unterblieb, hat eine am bisherigen Ort versuchte Zustellung (hier: vom 5. Mai 2012) nach Ablauf der üblichen Abholfrist praxisgemäss als erfolgt zu gelten (vgl. Urteile 2C_67/2008 vom 29. April 2008 E. 2.2 mit Hinweisen; 4F_17/2010 vom 7. März 2011; 6S.61/2006 vom 29. März 2006 E. 2). Demnach erfolgte die Beschwerde vom 24. September 2012 gegen den Einspracheentscheid vom 3. Mai 2012 offensichtlich verspätet. Dies selbst dann, wenn die Abholfrist gemäss der genannten Rechtsprechung zur Empfangspflicht um "wenige Wochen" (erwähntes Urteil 2C_1040/2012, 2C_1041/2012 E. 4.1) verlängert worden wäre.
4.3. Die Beschwerdeführer wenden ein, nach dem Grundsatz von Treu und Glauben nach <ref-law> müsse die Beschwerde als rechtzeitig erhoben gelten, weil durch die direkte Zustellung mittels Einschreiben vom 30. August 2012 berechtigtes Vertrauen geschaffen worden sei. Dazu hat das kantonale Gericht zutreffend erwogen, bei einer bereits abgelaufenen Frist werde durch die nachträgliche Information über die früheren Zustellversuche keine neue Frist ausgelöst. Dem ist beizufügen, dass nach Ablauf der Rechtsmittelfrist der Vertrauensschutz selbst bei - hier nicht gegebener - unzutreffender Information über die Frist nicht greift (erwähntes Urteil 9C_102/2016 E. 2).
5.
Schliesslich monieren die Beschwerdeführer, die Vorinstanz hätte die Beschwerde mutatis mutandis als Fristwiederherstellungsgesuch im Sinne von Art. 60 Abs. 2 in Verbindung mit <ref-law> entgegennehmen müssen bzw. habe die Voraussetzungen für eine Wiederherstellung der Frist zu Unrecht verneint. D ass sie zur Zeit der ersten direkten Zustellung ferienhalber abwesend gewesen seien, stelle ein unverschuldetes Hindernis dar. Die Beschwerdeführer verkennen in ihrer Argumentation, dass im Sozialversicherungsrecht des Bundes der in <ref-law> ausdrücklich verankerte Grundsatz gilt, dass der Versicherungsträger seine Mitteilungen an den Vertreter einer Partei zu richten hat, solange diese ihre Vollmacht nicht widerrufen hat. Dieser Grundsatz dient im Interesse der Rechtssicherheit dazu, allfällige Zweifel darüber zum Vornherein zu beseitigen, ob die Mitteilungen an die Partei selber oder an ihre Vertretung zu erfolgen haben, sowie um klarzustellen, welches die für einen Fristenlauf massgebenden Mitteilungen sein sollen (<ref-ruling> E. 3 S. 182; Urteil 9C_791/2010 vom 10. November 2010 E. 2.2 mit Hinweisen, in: SVR 2011 IV Nr. 32 S. 93). Entsprechend diesem Grundsatz war die erste Mitteilung an die bekannt gegebene Adresse des Rechtsvertreters fristauslösend (E. 4.2 hievor) und nicht die späteren (direkten) Zustellungen. Die (implizite) Abweisung des Gesuchs um Fristwiederherstellung ist demnach nicht zu beanstanden.
6.
Nach dem Gesagten hält der angefochtene Beschluss vor Bundesrecht stand. Die Beschwerde ist abzuweisen. Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.
7.
Dem Verfahrensausgang entsprechend gehen die Gerichtskosten zu Lasten der Beschwerdeführer; diese haften hierfür solidarisch (Art. 66 Abs. 1 und 5 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 1'000.- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 8. August 2016
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Glanzmann
Der Gerichtsschreiber: Furrer