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.

Considérant en droit:
1. La loi sur le Tribunal fédéral du 17 juin 2005 (LTF; RS 173.110) est entrée en vigueur le 1er janvier 2007 (RO 2006 1205, 1242). L'acte attaqué ayant été rendu avant cette date, la procédure reste régie par l'OJ (<ref-law>; <ref-ruling> consid. 1.2 p. 395).
2. Le jugement entrepris porte sur des prestations de l'assurance-invalidité, de sorte que le Tribunal fédéral examine uniquement si l'autorité cantonale de recours a violé le droit fédéral, y compris l'excès et l'abus du pouvoir d'appréciation, si les faits pertinents ont été constatés de manière manifestement inexacte ou incomplète ou s'ils ont été établis au mépris de règles essentielles de procédure (art. 132 al. 2 OJ [dans sa teneur selon le ch. III de la loi fédérale du 16 décembre 2005 portant modification de la LAI, en vigueur depuis le 1er juillet 2006], en relation avec les art. 104 let. a et b, ainsi que 105 al. 2 OJ).
3. 3.1 Aux termes de l'<ref-law>, lorsqu'il n'est demandé ni extrait de compte ni rectification, ou lorsqu'une demande en rectification a été rejetée, la rectification des inscriptions ne peut être exigée, lors de la réalisation du risque assuré, que si l'inexactitude des inscriptions est manifeste ou si elle a été pleinement prouvée. Il n'y a matière à rectification que si la preuve stricte (<ref-ruling> consid. 3d) est rapportée qu'un employeur a effectivement retenu des cotisations AVS sur les revenus versés ou qu'une convention de salaire net a été fixée entre cet employeur et le salarié (cf. aussi <ref-law>); établir l'exercice d'une activité lucrative salariée n'y suffit pas (cf. par exemple l'arrêt du Tribunal fédéral des assurances du 17 juillet 2006 (I 401/05, consid. 3).
3.2 En l'espèce, dans la mesure où l'assurée n'a pas été en mesure de produire ni attestation de salaire ni convention de salaire net pour la période de 1990 à fin juillet 1993, la preuve stricte que Me X._ avait effectivement retenu des cotisations sur son salaire pendant cette période n'a pas été rapportée. Contrairement à ce qu'ont retenu les premiers juges, le fait que l'employeur de l'intimée a prélevé des cotisations sur son salaire à partir du 1er août 1993 n'y change rien.
Au vu de ce qui précède, la preuve exigée par l'<ref-law> n'a pas été rapportée. Il s'ensuit qu'une rectification du compte individuel de l'assurée ne pouvait intervenir et c'est à juste titre que la caisse de compensation n'a pas tenu compte de cotisations pour la période de janvier 1990 à juillet 1993. C'est donc à tort que les juges cantonaux ont annulé la décision de l'office recourant du 9 janvier 2006 et prescrit à la caisse de compensation d'inscrire sur le compte individuel de l'assurée un revenu de 2'100 fr. par mois entre le 1er janvier 1990 et le 31 juillet 1993. Par conséquent, le recours de droit administratif est bien fondé.
4. Vu la nature du litige, la procédure est onéreuse (art. 134 2ème phrase OJ). L'intimée, qui succombe, supportera les frais de la procédure (art. 156 al. 1 en corrélation avec l'art. 135 OJ).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours de droit administratif est admis et la décision du Tribunal cantonal des assurances sociales de la République et canton de Genève du 3 octobre 2006 est annulée.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de l'intimée.
3. Le présent arrêt est communiqué aux parties, au Tribunal cantonal des assurances sociales de la République et canton de Genève, à l'Office fédéral des assurances sociales et à la Caisse interprofessionnelle AVS de la Fédération des Entreprises Romandes.
Lucerne, le 21 février 2008
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: La Greffière:
Meyer Fretz