Sachverhalt:
A.
A._, französischer Staatsangehöriger und wohnhaft in der Schweiz, ist seit Januar 1999 bei der Ausgleichskasse des Kantons Zürich als selbstständig Erwerbender erfasst. In den Jahren 2005 bis 2007 arbeitete er in Sofia, Bulgarien, für die niederländische Firma X._ mit Sitz in den Niederlanden. Gestützt auf Meldungen des kantonalen Steueramtes vom 20. September 2008 erliess die Ausgleichskasse des Kantons Zürich am 26. September 2008 drei Beitragsverfügungen für selbstständig Erwerbende sowie eine Verzugszinsverfügung für die Jahre 2005 bis 2007. Mit Einsprache machte A._ geltend, er sei als Arbeitnehmer in Bulgarien tätig gewesen und unterliege daher nicht der Beitragspflicht. Mit Einspracheentscheid vom 23. April 2010 wies die Ausgleichskasse die Einsprache ab, hob indessen die Beitragsverfügungen für selbstständig Erwerbende vom 26. September 2008 auf und verfügte am 7. Mai 2010 für die Jahre 2005 bis 2007 eine Beitragspflicht als Arbeitnehmer ohne beitragspflichtigen Arbeitgeber samt Verzugszinsberechnung.
B.
Die hiegegen erhobene Beschwerde hiess das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 29. November 2011 in dem Sinne gut, als es den Einspracheentscheid vom 23. April 2010 aufhob mit der Feststellung, dass der Beschwerdeführer für die Jahre 2005 bis 2007 in der Schweiz nicht AHV-beitragspflichtig ist.
C.
Die Ausgleichskasse des Kantons Zürich führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, der vorinstanzliche Entscheid sei aufzuheben und der Einspracheentscheid vom 23. April 2010 sei wiederherzustellen.
Das kantonale Gericht verzichtet auf eine Stellungnahme. A._ beantragt die Abweisung, soweit darauf einzutreten ist, das Bundesamt für Sozialversicherungen die Gutheissung der Beschwerde. Der Beschwerdegegner lässt am 20. August 2012 eine weitere Eingabe einreichen.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 1.2 S. 252 mit Hinweisen; <ref-ruling> E. 2.2 S. 550; <ref-ruling> E. 1.4 S. 140). Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.4.1 S. 254).
1.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Offensichtlich unrichtig im Sinne von <ref-law> ist die Sachverhaltsfeststellung, wenn sie willkürlich ist (<ref-ruling> E. 1.4.1 S. 39). Die entsprechende Rüge prüft das Bundesgericht nur insoweit, als sie in der Beschwerde explizit vorgebracht und substanziiert begründet worden ist.
2.
2.1. Gemäss <ref-law> sind natürliche Personen mit Wohnsitz in der Schweiz in der AHV obligatorisch versichert. Gemäss <ref-law> werden die Beiträge der erwerbstätigen Versicherten in Prozenten des Einkommens aus unselbstständiger und selbstständiger Erwerbstätigkeit festgesetzt (Abs. 1). Die Beiträge der Arbeitnehmer nicht beitragspflichtiger Arbeitgeber werden laut <ref-law> ebenfalls in Prozenten des massgebenden Lohnes festgesetzt.
2.2. Am 1. Juni 2002 ist das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit (FZA; SR 0.142.112.681) in Kraft getreten. Nach Art. 1 Abs. 1 des auf der Grundlage von Art. 8 FZA ausgearbeiteten und Bestandteil des Abkommens bildenden (Art. 15 FZA) Anhangs II ("Koordinierung der Systeme der sozialen Sicherheit") FZA in Verbindung mit Abschnitt A dieses Anhangs wenden die Vertragsparteien untereinander insbesondere die Verordnung (EWG) Nr. 1408/71 des Rates vom 14. Juni 1971 zur Anwendung der Systeme der sozialen Sicherheit auf Arbeitnehmer und Selbstständige sowie deren Familienangehörige, die innerhalb der Gemeinschaft zu- und abwandern (kurz: VO Nr. 1408/71; SR 0.831.109.268.1), und die Verordnung (EWG) Nr. 574/72 des Rates vom 21. März 1972 über die Durchführung der VO (EWG) Nr. 1408/71 über die Anwendung der Systeme der sozialen Sicherheit auf Arbeitnehmer und Selbstständige sowie deren Familienangehörige, die innerhalb der Gemeinschaft zu- und abwandern (kurz: VO Nr. 574/72; SR 0.831.109.268.11), oder gleichwertige Vorschriften an. Die VO Nr. 1408/71 gilt unter anderem auch für Rechtsvorschriften über Zweige der sozialen Sicherheit, die Leistungen bei Alter und an Hinterbliebene betreffen (Art. 4 Abs. 1 lit. c und d). Die entsprechenden Bestimmungen finden in der Alters- und Hinterlassenenversicherung durch den Verweis in <ref-law> Anwendung.
2.3. Titel II der Verordnung Nr. 1408/71 (Art. 13 bis 17a) enthält allgemeine Kollisionsregeln zur Bestimmung der anzuwendenden Rechtsvorschriften. Dabei legt Art. 13 Abs. 1 den kollisionsrechtlichen Grundsatz der Einheitlichkeit der anwendbaren Rechtsvorschriften nach den Regeln gemäss Art. 13 Abs. 2 bis Art. 17a in dem Sinne fest, dass für jede betroffene Person die Rechtsvorschriften nur eines Mitgliedstaates massgebend sind (<ref-ruling> E. 3.1 S. 537 und 258 E. 4.2 S. 263 f. mit Hinweis). Ausnahmen vorbehalten, gilt für Arbeitnehmende das Beschäftigungslandprinzip. Dies trifft auch dann zu, wenn sie im Gebiet eines anderen Mitgliedstaates wohnen oder ihr Arbeitgeber oder das Unternehmen, das sie beschäftigt, den Wohn- oder Betriebssitz im Gebiet eines anderen Mitgliedstaates hat (Grundsatz der lex loci laboris; Art. 13 Abs. 2 lit. a der Verordnung Nr. 1408/71; <ref-ruling> E. 3.1 S. 537 und 258 E.4.2 S. 263 f. mit Hinweis). Eine Ausnahme ist unter anderem vorgesehen für eine Person, die in mehreren Mitgliedstaaten abhängig beschäftigt oder selbstständig tätig ist. Handelt es sich hierbei um eine Person, die nicht als Mitglied des fahrenden oder fliegenden Personals eines Unternehmens beschäftigt ist, unterliegt sie den Rechtsvorschriften des Mitgliedstaates, in dessen Gebiet sie wohnt, wenn sie ihre Tätigkeit zum Teil im Gebiet dieses Staates ausübt oder wenn sie für mehrere Unternehmen oder mehrere Arbeitgeber tätig ist, die ihren Sitz oder Wohnsitz im Gebiet verschiedener Mitgliedstaaten haben (Art. 14 Abs. 2 lit. b/i). Sodann unterliegt sie den Rechtsvorschriften des Mitgliedstaates, in dessen Gebiet das Unternehmen oder der Arbeitgeber, das bzw. der sie beschäftigt, seinen Sitz oder Wohnsitz hat, sofern sie nicht im Gebiet eines Mitgliedstaates wohnt, in denen sie ihre Tätigkeiten ausübt (Art. 14 Abs. 2 lit. b/ii).
3.
3.1. Die Vorinstanz erwog, der Beschwerdegegner falle als französischer Staatsangehöriger mit Wohnsitz in der Schweiz grundsätzlich in den persönlichen Geltungsbereich des FZA sowie der Verordnungen, auf die das Abkommen verweist. Am 1. Juni 2009 habe das FZA eine räumliche Ausdehnung zufolge des Beitritts von Rumänien und Bulgarien erfahren. Die Tätigkeit des Beschwerdegegners übe dieser für einen niederländischen Arbeitgeber in Bulgarien aus, das in der fraglichen Zeitspanne 2005 bis 2007 (noch) kein Mitglied-, sondern ein Drittstaat gewesen sei. Eine solche Konstellation sei vom Bundesgericht noch nie entschieden worden; in <ref-ruling> habe es sich zwar ebenfalls um ein räumliches Dreiecksverhältnis gehandelt, wobei es sich dort bei sämtlichen Staaten um Mitgliedstaaten gehandelt habe. Eine vergleichbare Konstellation habe indes der Gerichtshof der Europäischen Gemeinschaften (EuGH) in der Rechtssache C-60/93 Aldewereld entschieden. Dort sei ein Wanderarbeiter zwar von einem Unternehmen aus der Gemeinschaft eingestellt worden, aber nicht auf dem Gebiet der Gemeinschaft tätig gewesen. Der EuGH sei von einer Lücke in der Verordnung 1408/71 ausgegangen, weil die Verordnung sich nicht auf einen Wanderarbeiter beziehe, der zwar von einem Unternehmen aus der Gemeinschaft eingestellt werde, aber nicht im Gebiet der Gemeinschaft tätig sei. In einer solchen Situation seien der Wohnsitz des Arbeitnehmers oder der Ort, an dem der Arbeitgeber ansässig sei, die einzigen möglichen Anknüpfungspunkte. Der EuGH entschied sich als Anknüpfungspunkt für die Anwendung der Rechtsvorschriften desjenigen Staates, in dem der Arbeitgeber ansässig sei. Übertragen auf den vorliegenden Fall bedeute dies, so die Würdigung der Vorinstanz, dass der Beschwerdegegner der schweizerischen Beitragspflicht nicht unterstellt sei.
3.2. Die Ausgleichskasse führte aus, der Beschwerdegegner habe als unselbstständiger Arbeitnehmer der niederländischen Unternehmung in Bulgarien gearbeitet; es liege keine Entsendung im Sinne des Freizügigkeitsabkommens vor, denn Bulgarien sei zur strittigen Zeit nicht Mitgliedstaat gewesen. Der Beschwerdegegner sei nicht der niederländischen Sozialversicherung unterstellt gewesen; dies gehe aus den in der Einsprache ins Recht gelegten Lohnausweisen hervor. Dort seien Zahlungen an die ARRCO ("Association pour le régime de retraite complémentaire des salariés") und AGIRC ("Association générale des institutions de retraite des cadres") ausgewiesen; das seien französische Zusatzpflichtrentenversicherungen, welche die Grundrenten ergänzten. Entsprechend sei für die Frage, welchem Sozialversicherungsrecht der Beschwerdegegner unterstellt sei, einzig das Verhältnis zwischen der Schweiz und Bulgarien massgeblich. Deshalb sei das FZA nicht anwendbar, und in der Folge könne auch das als Parallelfall angerufene Urteil Aldewereld des EuGH nicht Grundlage für den vorliegenden Rechtsstreit sein. Der Beschwerdegegner habe nie in den Niederlanden gearbeitet und sei auch nie der niederländischen Sozialversicherung angeschlossen gewesen. Auch das am 1. Dezember 2007 in Kraft getretene Sozialversicherungsabkommen zwischen der Schweiz und Bulgarien sei nicht anwendbar, da diesem nur schweizerische und bulgarische Bürger unterstellt seien.
3.3. Das Bundesamt für Sozialversicherungen macht in seiner Stellungnahme wie die Ausgleichskasse geltend, der Beschwerdegegner sei durch seine Tätigkeit für die niederländische Unternehmung X._ nicht der niederländischen Sozialversicherung angeschlossen gewesen. Die Lohnabzüge würden von der niederländischen Arbeitgeberin ausdrücklich in jährlichen Bestätigungen ausgeführt, wobei es sich um eine freiwillige Versicherung Frankreichs handle. Die niederländische Arbeitgeberin des Beschwerdegegners habe diejenigen Beiträge übernommen, die der Beschwerdegegner selber in seinem Heimatland Frankreich freiwillig hätte bezahlen können. Es liege somit keine unzumutbare Doppelversicherung vor, weshalb sich eine Anlehnung an die EuGH-Entscheidung in der Rechtssache Aldewereld verbiete. Dort habe zur Vermeidung einer Doppelversicherung eine Entscheidung zugunsten der Rechtsvorschriften am Sitz der Arbeitgeberin gefällt werden müssen, denn, so jener Entscheid, eine doppelte Beitragspflicht würde einer Grundzielsetzung des Abkommens entgegenstehen und sei daher zu vermeiden. Zwischen den Niederlanden und Bulgarien würde im Übrigen kein Sozialversicherungsabkommen bestehen. Selbst für den letzten Monat der strittigen Beitragsperiode (Dezember 2007), in dem das Sozialversicherungsabkommen zwischen der Schweiz und Bulgarien in Kraft getreten sei, gelte keine andere Regelung, weil gemäss Art. 3 Ziff. 3 in Verbindung mit Art. 6 des Abkommens das Erwerbsortsprinzip für Drittstaatsangehörige nicht gelte.
3.4. Der Beschwerdegegner lässt ausführen, als französischer Staatsangehöriger mit Wohnsitz in der Schweiz falle er in den Anwendungsbereich des FZA und der Verordnung 1408/71, weshalb sich die hier anwendbaren Rechtsvorschriften nach Art. 13 ff. der Verordnung 1408/71 richten würden. Die Tätigkeit in einem Drittstaat sei von der Verordnung 1408/71 jedoch nicht abgedeckt. Eine solche Konstellation entspreche der Rechtssache Aldewereld des EuGH (C-60/93). Indem das kantonale Gericht sich auf diese Entscheidung berufen habe, habe es kein Bundesrecht verletzt. Die Vorinstanz habe für das Bundesgericht verbindlich, das heisst nicht offensichtlich unrichtig festgestellt, dass der Beschwerdegegner aus dem Arbeitsverhältnis mit der niederländischen Unternehmung X._ - nach Abzug von Steuern und Sozialabgaben - sein Einkommen generiert habe. Im Übrigen könne die Beschwerdeführerin mit der Rüge, dass dem Beschwerdegegner keine Beiträge für die niederländische Sozialversicherung abgezogen worden seien, nichts zu ihren Gunsten ableiten.
4.
4.1. Die Parteien und die Vorinstanz sind sich - gestützt auf das Urteil Aldewereld des EuGH (C-60/93) - darin einig, dass die Koordinationsbestimmungen der VO 1408/71 des FZA die hier vorliegende Konstellation, in der zwar sowohl der Wohnsitz des Arbeitnehmers als auch der Sitz der Arbeitgeberin in unterschiedlichen Mitgliedstaaten (bzw. dem Vertragsstaat Schweiz) liegen, der Erwerbsort hingegen in einem Drittstaat liegt, nicht regeln. In den massgeblichen Jahren 2005 bis 2007 war Bulgarien, wie die Vorinstanz ebenfalls zutreffend erwog, noch nicht Mitgliedstaat des Europäischen Wirtschaftsraums. Dass bei fehlender Regelung in den Koordinationsbestimmungen die Rechtsprechung des EuGH als Leitlinie konsultiert wird, ist ebenfalls nicht bestritten und entspricht der bundesgerichtlichen Rechtsprechung (vgl. u.a. <ref-ruling> E. 5 S. 433, E. 8 S. 437, Art. 16 Abs. 2 FZA). Einer näheren Prüfung bedarf daher die Rechtsfrage, ob der EuGH-Entscheid in der Rechtssache Aldewereld, wie die Vorinstanz erwog, vorliegend richtungweisende Grundlage sein könnte.
4.2. Strittig war in jenem Entscheid die Frage, ob Herr Aldewereld (auch) in den Niederlanden Sozialversicherungsbeiträge bezahlen müsse. Er war niederländischer Staatsangehöriger, der im Zeitpunkt seiner Anstellung durch ein in Deutschland ansässiges Unternehmen in den Niederlanden wohnte. Dieses deutsche Unternehmen schickte ihn nach Thailand zur Arbeit. Wegen dieser Tätigkeit war Herr Aldewereld der deutschen Sozialversicherung unterstellt, die entsprechenden Beiträge wurden ihm vom Lohn abgezogen (Ziff. 3 und 4 des Urteils vom 29. Juni 1994, C-60/93, Slg. 1994 I-02991). Der Gerichtshof führte aus, dass "bei Fehlen einer Bestimmung, die sich ausdrücklich auf den Fall einer Person in der Situation des Herrn Aldewereld bezieht, eine solche Person nach dem System der Verordnung den Rechtsvorschriften des Mitgliedstaats unterliegt, in dem der Arbeitgeber ansässig ist" (Randnr. 25 des Entscheids). Die Vorschriften des Gemeinschaftsrechts, die die Verwirklichung der Freizügigkeit der Arbeitnehmer in der Gemeinschaft bezwecken, würden es verbieten "dass von einem Arbeitnehmer, der im Gebiet eines Mitgliedstaats wohnt und im Rahmen eines Arbeitsverhältnisses mit einem in einem anderen Mitgliedstaat ansässigen Unternehmen ausschliesslich ausserhalb des Gebiets der Mitgliedstaaten Tätigkeiten ausübt, aufgrund derer er nach den sozialen Rechtsvorschriften dieses anderen Mitgliedstaats beitragspflichtig ist, Beiträge nach den sozialen Rechtsvorschriften seines Wohnstaats erhoben werden". Mit anderen Worten: Herr Aldewereld ist der deutschen Sozialversicherung unterstellt; eine zweite Unterstellung an seinem Wohnort läuft dem Zweck der Abkommen - Freizügigkeit der Arbeitnehmer - zuwider, weshalb ausschliesslich der Sitz der Arbeitgeberin Anknüpfungspunkt ist.
4.3. Der Beschwerdegegner untersteht sowohl in persönlicher als auch in sachlicher Hinsicht der VO Nr. 1408/71. Dessen Art. 13 Abs. 1 hält als Grundsatz fest, dass die Rechtsvorschriften nur eines Mitgliedstaats anwendbar sind (<ref-ruling> E. 3.1 S. 537 und 258 E. 4.2 S. 263 f. mit Hinweis). Ausgehend von diesem Grundsatz ist der zuständige Mitgliedstaat zu ermitteln. Der in der Schweiz wohnhafte Beschwerdegegner war in den Jahren 2005 bis 2007 für einen Arbeitgeber in den Niederlanden in einem Drittstaat (Bulgarien) erwerbstätig. Wohnsitz des Arbeitnehmers und Sitz des Arbeitgebers befinden sich in einem Abkommensstaat, während die unselbstständige Erwerbstätigkeit in einem Drittstaat ausgeübt wurde. Diese Konstellation ist mit dem in der Rechtssache Aldewereld (C-60/93) beurteilten Sachverhalt identisch. Im Urteil Aldewereld hatte der Versicherte in einem Mitgliedstaat Wohnsitz (Niederlande) und war für einen in einem andern Mitgliedsstaat ansässigen Arbeitgeber (Deutschland) in einem Drittstaat (Thailand) erwerbstätig. Der EuGH knüpfte für die Koordination entscheidend auf den Sitz des Arbeitgebers an. Entgegen der Auffassung des Bundesamtes für Sozialversicherungen ist das Urteil Aldewereld nicht nur auf den Tatbestand der Entsendung (vgl. auch Art. 14 Abs. 1 VO 1408/71) anwendbar. Die dem EuGH vorgelegte Rechtsfrage war generell formuliert (Ziff. 8) und wurde generell beantwortet (Ziff. 26 des Urteils vom 29. Juni 1994, C-60/93; vgl. auch Ziff. 11). Im vorliegenden Fall ist daher mit der Vorinstanz auf das Urteil in der Rechtssache Aldewereld (C-60/93) abzustellen. Der Sitz des Arbeitgebers in den Niederlanden ist als Anknüpfungspunkt naheliegender als der Wohnsitz des Beschwerdegegners in der Schweiz, der mit dem Arbeitsverhältnis, dem Arbeitsort und dem Sitz des Arbeitgebers in keinem Zusammenhang steht (Steinmeyer, in: Fuchs [Hrsg.], Europäisches Sozialrecht, 4. Aufl. 2005, S. 173 N. 2 am Ende). Aus diesem Grund ist die Koordination zugunsten der Niederlande vorzunehmen, deren System der sozialen Sicherheit Anwendung findet. Denn nach Art. 14 Abs. 2 lit. b/ii VO 1408/71 in Verbindung mit dem Urteil Aldewereld unterliegt eine Person den Rechtsvorschriften des Mitgliedstaats, in dessen Gebiet das Unternehmen oder der Arbeitgeber, das bzw. der sie beschäftigt, seinen Sitz oder Wohnsitz hat, sofern sie nicht im Gebiet eines der Mitgliedstaaten wohnt, in denen sie die Tätigkeit ausübt. Für Schweizer Recht verbleibt unter diesen Umständen kein Raum, und zwar unabhängig davon, ob und wie die Niederlande als zuständiger Staat das Einkommen aus Bulgarien behandelt. Ob und inwieweit der Beschwerdegegner in den Niederlanden tatsächlich der Beitragspflicht untersteht, ist ohne Belang. Denn selbst wenn die Niederlande als zuständiger Staat von einer Beitragspflicht für das in Bulgarien erzielte Einkommen absieht, kann sich die Schweiz nicht über die kollisionsrechtliche Regelung hinwegsetzen und die Beitragspflicht für sich beanspruchen. Die Verordnung dient dazu, die im konkreten Fall anwendbare Sozialrechtsordnung zu finden (Fuchs [Hrsg.], Europäisches Sozialrecht, 4. Aufl., S. 19 N. 58), sie bezweckt hingegen nicht, in jedem Fall eine Unterstellung unter eine Beitragspflicht vorzunehmen.
5.
Bei diesem Ausgang des Verfahrens wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 21. März 2013
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Der Gerichtsschreiber: Nussbaumer