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.