Faits: A. Par décision du 23 septembre 2005, l'Office cantonal de l'assurance-invalidité de Genève (ci-après: l'OCAI) a octroyé à M._ une rente entière d'invalidité à partir du 1er juin 2004, fondée sur un revenu annuel moyen de 39'990 fr. et une durée de cotisations de dix ans et sept mois, entraînant l'application de l'échelle de rente 16. L'intéressée a formé opposition contre cette décision, contestant le calcul de sa rente. Selon ses dires, elle avait travaillé de janvier 1990 à fin juillet 2000 en qualité d'employée de maison au service de X._, avocat. A réception de la décision de rente, elle s'était aperçue qu'entre janvier 1990 et juillet 1993 aucune cotisation sociale n'avait été acquittée en sa faveur par son ancien employeur. Elle demandait dès lors un nouveau calcul de sa rente tenant compte des cotisations manquantes. Se fondant notamment sur un prévis de la Caisse interprofessionnelle AVS de la Fédération des Entreprises Romandes (ci-après: la caisse de compensation) qui avait calculé le montant de la rente d'invalidité, l'OCAI a rejeté l'opposition de l'assurée et confirmé sa décision du 23 septembre 2005 (cf. décision sur opposition du 9 janvier 2006). B. M._ a recouru contre la décision sur opposition du 9 janvier 2006 devant le Tribunal cantonal des assurances sociales de Genève. Au cours de l'instruction, la Présidente de la 2ème chambre du Tribunal a recueilli un certificat de travail établi le 16 août 2000 par Me X._, duquel il ressort que l'assurée était employée par ce dernier "depuis 1990 environ jusqu'au 31 juillet 2000". Me X._ a en outre précisé, par courrier du 24 avril 2006, qu'il ne se souvenait pas que le contrat de travail conclu avec l'assurée avait été modifié, si ce n'est sous forme de plusieurs augmentations successives de salaire. Dans son jugement du 3 octobre 2006, la juridiction cantonale considéra qu'en l'absence de modification du contrat de travail, il y avait lieu de considérer que les cotisations sociales avaient été prélevées entre le 1er janvier 1990 et le 31 juillet 1993, comme cela avait été le cas par la suite, même si l'employeur ne les avait pas reversées à la caisse de compensation. Elle en a conclu que la preuve du prélèvement de cotisations pendant les années 1990 à 1993 avait été rapportée. Aussi, la juridiction cantonale a admis le recours de l'assurée. Elle a annulé la décision de l'OCAI du 9 janvier 2006, dit que des cotisations sociales étaient réputées avoir été prélevées sur un salaire mensuel brut de 2'100 fr. du 1er janvier 1990 au 31 juillet 1993 et condamné la caisse de compensation - appelée en cause devant l'instance cantonale - à inscrire lesdits revenus sur le compte individuel de l'assurée. C. L'OCAI a interjeté un recours de droit administratif contre ce jugement dont il a demandé l'annulation. M._ a conclut au rejet du recours, tandis que l'Office fédéral des assurances sociales a proposé son admission.