Faits: A. Le 9 février 2011, le Ministère public du canton de Genève (ci-après: le Ministère public) a ouvert une procédure pénale contre inconnu pour blanchiment d'argent et ordonné le séquestre pénal de divers documents concernant la société X._. L'instruction, qui vise notamment C._, a été étendue aux infractions d'abus de confiance, faux dans les titres et blanchiment d'argent aggravé. Il est reproché au prénommé de s'être approprié indûment des fonds qui lui avaient été confiés via la société précitée. Les 4 octobre et 2 novembre 2010, X._ a effectué deux versements pour un total de 32'557,05 fr. en faveur de l'avocat B._, à titre de provisions et honoraires. A la fin du mois de février 2011, X._ et C._ ont mandaté l'avocat A._ dans le cadre de plusieures affaires civiles. A cet effet, une provision de 55'000 fr. a été versée par X._ sur le compte de l'avocat en question. Les mandats ont pris fin en mai 2011 et les notes d'honoraires finales ont laissé apparaître un solde de 11'084 fr. en faveur de X._. Le 9 août 2011, le Ministère public a invité A._ à produire ses notes d'honoraires, en l'informant du fait qu'il ordonnait le séquestre conservatoire du solde de la provision versée. Statuant sur recours de C._, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a considéré, par arrêt du 25 janvier 2012, que l'entier des provisions versées à A._ par X._ devait être séquestré. Donnant suite à cet arrêt, le Ministère public a ordonné le séquestre conservatoire des 55'000 fr. versés à l'avocat prénommé, par ordonnance du 9 mars 2012. Se fondant sur l'art. 263 du code de procédure pénale suisse (CPP; RS 312.0), il évoquait le paiement d'une créance compensatrice au sens de l'art. 71 du code pénal suisse (CP; RS 311.0). Par décision du même jour, le Ministère public a ordonné le séquestre pénal conservatoire des 32'557,05 fr. versés à B._. B. A._ et B._ ont recouru contre ces ordonnances auprès de la Cour de justice, qui a rejeté leurs recours par arrêt du 16 mai 2012. Cette autorité a considéré en substance que A._ ne pouvait pas bénéficier de l'art. 70 al. 2 CP dans la mesure où les fonds détournés avaient été utilisés directement pour le payer. Quant à B._, il ne pouvait pas se prévaloir du fait que son mandat concernait uniquement la société X._, les comptes bancaires de cette société ayant été utilisés par C._ pour commettre un abus de confiance et la somme séquestrée provenant du compte sur lequel les investisseurs dupés ont versé leur argent. C. Agissant par la voie du recours en matière pénale, A._ (cause 1B_365/2012) demande au Tribunal fédéral d'annuler cet arrêt, de lever le séquestre à hauteur de 43'916 fr., d'ordonner le séquestre conservatoire à hauteur de 11'084 fr., subsidiairement de renvoyer la cause à l'instance précédente pour nouvelle décision. Il requiert en outre l'octroi de l'effet suspensif. B._ forme lui aussi un recours en matière pénale (cause 1B_367/2012), concluant à l'annulation de l'arrêt attaqué, subsidiairement au renvoi de la cause à l'instance précédente pour nouvelle décision. Au terme de ses observations, le Ministère public s'en remet à justice s'agissant du bien-fondé des recours. La Cour de justice se réfère simplement à son arrêt. B._ a formulé des observations complémentaires, A._ y a renoncé. D. Par ordonnance du 25 juillet 2012, le Président de la Ire Cour de droit public a rejeté la requête d'effet suspensif présentée dans la cause 1B_365/2012.