Faits: A. Sur réquisition du 10 août 2011 de A._, agissant pour Z._ SA, l'Office des poursuites de Genève (ci-après: l'office) a fait notifier, le 9 septembre 2011, à X._ SA un commandement de payer (poursuite no 00 000000 U) trois montants distincts de 75'000 fr., avec intérêts à 5% respectivement dès les 31 décembre 2006, 2007 et 2008. Ce commandement de payer indiquait sous la rubrique titre et date de la créance, cause de l'obligation: " 1) Atteinte au crédit, 2) Fausse facturation avec inscription fallacieuse et illicite par l'administrateur de Z._ SA, M. Y._, administrateur de X._ SA, 3) Abus de confiance ". La débitrice y a fait opposition. Egalement sur réquisition du 10 août 2011 de A._, agissant pour Z._ SA, l'office a fait notifier, le 9 septembre suivant, à X._ SA un deuxième commandement de payer (poursuite no 00 000000 T) la somme de 321'015 fr. 85, plus intérêts à 5% dès le 20 février 2010. L'acte de poursuite mentionnait sous la rubrique titre et date de la créance, cause de l'obligation: " 1) Remboursement sur facturation indue, facturation illicite et abus du mandat d'administrateur de Z._ SA, 2) Atteinte au crédit ". La débitrice y a fait opposition. Toujours sur réquisition du 10 août 2011 de A._, agissant pour Z._ SA, l'office a fait notifier, le 12 septembre 2011, à Y._, un commandement de payer (poursuite no 00 000000 W) portant sur 42'000 fr., avec intérêts à 5% dès le 1er janvier 1998, 18'000 fr. avec intérêts à 5% dès le 1er janvier 2009 et 24'862 fr. 45, avec intérêts à 5% dès le 1er janvier 2010. La rubrique titre et date de la créance, cause de l'obligation indiquait: " 1) Rbt avance à Y._ pour travaux xxx (1997), 2) Rbt avance à Y._ pour travaux villa yyy, 3) Rbt avance à Y._ pour indemnité zzz selon décision du tribunal ". Il y a été fait opposition. Enfin, toujours sur réquisition du 10 août 2011 du même créancier, l'office a fait notifier, le 15 septembre 2011, derechef à Y._ un dernier commandement de payer (poursuite no 00 000000 V) le montant de 1'546'000 fr., sans intérêt. Sous la rubrique titre et date de la créance, cause de l'obligation figuraient comme indications: " 1) Prélèvement indu avec abus de la signature sociale de la société, 2) enrichissement illégitime et concurrence déloyale en tant qu'administrateur de la SA, 3) Atteinte au crédit ". Il y a aussi été fait opposition. B. B.a Le 19 septembre 2011, Y._ et X._ SA ont formé plainte contre les notifications, les 9 et 12 septembre 2011, des trois premiers commandements de payer susmentionnés devant la Chambre de surveillance de l'office, motifs pris que ces poursuites, fondées sur des créances contestées ou inexistantes, étaient constitutives d'un abus de droit et n'avaient aucun autre but que celui de les tourmenter délibérément. Ils ont soutenu en particulier qu'elles faisaient en effet suite à des poursuites qu'ils avaient eux-mêmes notifiées à A._, administrateur de Z._ SA, en paiement de dépens auxquels celui-ci avait été condamné. Elles s'inscrivaient ainsi dans un contexte de représailles ayant pour seul but de leur nuire dans le cadre de leur activité de promotion immobilière. Les plaignants ont requis l'apport en procédure d'un extrait des poursuites pendantes à l'encontre de Z._ SA. Le 26 septembre 2011, Y._ et X._ SA ont déposé une seconde plainte dirigée cette fois contre la notification, le 15 septembre 2011, du dernier commandement de payer. Ils ont invoqué les mêmes motifs que dans leur précédente plainte. B.b Dans ses observations des 22 septembre et 3 octobre 2011, l'office a conclu au rejet de ces plaintes, motifs pris que l'abus de droit allégué n'était pas manifeste et qu'il n'appartenait par ailleurs pas aux autorités de poursuite de revoir la justification des créances à l'origine de la procédure de réalisation forcée. Le 17 octobre 2011, Z._ SA a aussi proposé le rejet des plaintes et déposé diverses pièces. Y._ et X._ SA ont répliqué par écriture du 30 novembre 2011, reçue par le greffe le 1er décembre suivant. Ils ont par ailleurs produit un jugement du Tribunal de première instance du 13 octobre 2011 attribuant à X._ SA le 50% du capital actions de Z._ SA. Sur interpellation de la Chambre de surveillance des offices des poursuites et faillites, l'office a fait parvenir à cette autorité, le 27 février 2012, les copies des réquisitions de poursuite susmentionnées introduites par A._ pour le compte de Z._ SA à l'encontre de X._ SA et Y._, ainsi que l'extrait informatique du Registre du commerce concernant Z._ SA, imprimé le 24 février 2012. Dans la lettre du 24 février 2012 accompagnant cet envoi, il s'est déterminé sur un argument de la réplique des plaignants qui se fondait sur le jugement du 13 octobre 2011 attribuant à X._ SA le 50% du capital actions de Z._ SA. Il s'est référé, pour le surplus, à ses précédentes observations. Par courrier du 13 mars 2012 reçu le lendemain, Z._ SA a pris position sur cette détermination et a versé diverses pièces au dossier. Le 16 avril 2012, Y._ et X._ SA ont déposé de nouvelles observations en relation notamment avec le rapport complémentaire de l'office du 24 février précédent. B.c Par décision du 14 juin 2012, la Cour de justice du canton de Genève, statuant en sa qualité de Chambre de surveillance des Offices des poursuites et faillites, a préalablement ordonné la jonction des causes et l'apport au dossier de l'extrait des poursuites à l'encontre de Z._ SA. Au fond, elle a rejeté les plaintes. C. Par écriture du 29 juin 2012, Y._ et X._ SA exercent un recours en matière civile au Tribunal fédéral. Ils concluent principalement à l'annulation de la décision cantonale et à sa réforme en ce sens que les poursuites litigieuses sont annulées. Ils demandent subsidiairement que le dossier soit retourné à l'autorité cantonale pour nouvelle décision au sens des considérants. Z._ SA propose le rejet du recours. Ni la Chambre de surveillance ni l'office ne se sont déterminés.