Faits:
A. A la requête de la Compagnie Noga SA d'Importation et d'Exportation SA (ci-après: Noga SA), l'Office des poursuites de Genève (ci-après : l'Office) a notifié le 27 février 2003 à la Fédération de Russie un commandement de payer la somme de 1'185'600'000 CHF (poursuite n° 03 116.062 A), contre-valeur de la somme de 800'000'000 USD que la Fédération de Russie s'était engagée à payer à Noga SA en vertu d'un Protocole d'accord conclu le 31 juillet 2002 entre les parties.
Par jugement du 7 juillet 2003, le Tribunal de première instance de Genève a levé provisoirement l'opposition à cette poursuite formée par la Fédération de Russie.
Vu la clause d'arbitrage insérée dans le Protocole d'accord du 31 juillet 2002, la Fédération de Russie a, le 30 juillet 2003, ouvert une action en libération de dette devant la Cour internationale d'arbitrage de la CCI à Paris.
B. Le 22 décembre 2003, la Présidente du Tribunal de première instance de Genève, saisie d'une requête de Noga SA, a rendu une ordonnance de séquestre (n° 03 070.378 G) à l'encontre de la Fédération de Russie pour la totalité de la créance invoquée, soit 1'185'600'000 fr.
C. Le 13 octobre 2004, Noga SA a requis la continuation de la poursuite n° 03 116.062 A. L'Office a donné suite à cette réquisition en procédant à une saisie provisoire. Par décision du 3 mars 2005, la Commission de surveillance des offices des poursuites et des faillites du canton de Genève a rejeté la plainte formée par la Fédération de Russie contre cette décision.
D. Le 5 juin 2007, le Tribunal arbitral a rendu une sentence à la majorité de ses membres, à teneur de laquelle notamment la créance visée par la poursuite n° 03 116.062 A en Suisse a été déclarée en l'état inexistante, faute de réalisation, à la date du prononcé de la sentence, de la condition à laquelle est subordonnée l'efficacité du Protocole d'accord du 31 juillet 2002.
Le 5 juillet 2007, Noga SA a déposé une requête en correction et interprétation de la sentence arbitrale rendue le 5 juin 2007.
Dans un document appelé "Addendum" daté du 17 octobre 2007, le Tribunal arbitral a partiellement admis la requête en correction d'erreurs matérielles et a rejeté la requête en interprétation.
Le 14 décembre 2007, Noga SA a requis la continuation de la poursuite n° 03 116.062 A.
E. Le 8 janvier 2008, la Fédération de Russie a demandé la reconnaissance en Suisse de la sentence arbitrale du 5 juin 2007.
Par jugement du 13 mars 2008, le Tribunal de première instance de Genève a reconnu le "jugement" rendu le 5 juin 2007 par la Cour internationale d'arbitrage de la CCI à Paris dans la cause divisant la Fédération de Russie d'avec Noga SA.
Le 7 août 2008, la Cour de justice du canton de Genève a rejeté l'appel formé par Noga SA et a confirmé le jugement de première instance. Contre l'arrêt cantonal, Noga SA a interjeté auprès du Tribunal fédéral un recours, qui a été rejeté le 9 décembre 2008 (arrêt 4A_403/2008).
F. Par décision du 7 août 2009, l'Office a rejeté la réquisition de continuer la poursuite déposée le 14 décembre 2007, annulé la saisie provisoire requise le 13 octobre 2004, révoqué toutes les mesures relevant de l'exécution de la saisie provisoire et constaté la caducité de la poursuite n° 03 116.062 A.
Noga SA a, le 20 août 2009, formé une plainte contre cette décision, concluant principalement à son annulation, à la continuation de la poursuite n° 03 116062 A et à ce qu'il soit dit que la saisie provisoire et le séquestre n° 03 070378 G soient convertis en saisie définitive.
Statuant le 4 février 2010, la Commission de surveillance a rejeté la plainte.
G. Le 15 février 2010, Noga SA a déposé contre cette décision un recours en matière civile au Tribunal fédéral. Elle reprend, à titre principal, les conclusions principales formulées devant la Commission de surveillance. Subsidiairement, elle demande le maintien de la saisie provisoire et du séquestre jusqu'au terme d'une procédure arbitrale complémentaire ouverte devant le Tribunal arbitral dans le but d'"apporter la preuve de la réalisation de la condition dont il est question dans la sentence du 5 juin 2007".
Sur requête de la recourante, la Présidente de la Cour de céans a accordé l'effet suspensif au recours.
La Commission de surveillance s'est référée aux considérants de son arrêt et l'Office des poursuites a renoncé à se déterminer. Quant à la Fédération de Russie, elle a conclu au rejet du recours.

Considérant en droit:
1. Déposé en temps utile (<ref-law>) contre une décision finale (<ref-law>; <ref-ruling> consid. 1.2) rendue par une autorité de surveillance en matière de poursuite pour dettes statuant en dernière instance cantonale (<ref-law>), le présent recours en matière civile est recevable, indépendamment de la valeur litigieuse (art. 74 al. 2 let. c LTF).
2. La recourante demande préalablement au Tribunal fédéral de surseoir à statuer jusqu'à droit connu "sur la procédure complémentaire d'arbitrage tendant à démontrer que la condition suspensive imaginée par le Tribunal arbitral est avenue".
En vertu des <ref-law> et 6 al. 1 PCF, l'examen du recours peut être suspendu pour des raisons d'opportunité, notamment lorsque le jugement d'un autre litige peut influencer l'issue du procès (cf. FLORENCE AUBRY GIRARDIN, in : Commentaire de la LTF, 2009, n° 9 ad <ref-law> et les arrêts cités; cf. PHILIPPE GELZER, Commentaire bâlois, n. 5 ad <ref-law>). Une requête de suspension doit être motivée, sous peine d'irrecevabilité (cf. <ref-law>; FLORENCE AUBRY GIRARDIN, op. cit., n. 5 ad <ref-law> et les réf. citées).
En l'occurrence, la requête de suspension devient sans objet avec le présent arrêt. Au demeurant, il appartenait au recourant, pour répondre aux exigences de motivation, d'exposer en quoi l'issue de cette prétendue "procédure complémentaire d'arbitrage" aurait une influence sur l'issue du présent litige, ce qu'il ne fait pas à l'appui de sa requête de suspension. En outre, à supposer qu'il ait effectivement introduit une nouvelle procédure arbitrale en vue de faire constater l'existence de sa créance, il s'agirait d'un fait nouveau dont la Cour de céans ne pourrait tenir compte dans le cadre du présent litige (<ref-law>). En tout état de cause, comme on le verra ci-dessous (consid. 3), ce nouveau procès ne saurait influencer l'issue de la présente procédure. Pour ces différents motifs, la requête de suspension, actuellement sans objet, était vouée à l'échec.
3. La recourante reproche à l'Office d'avoir considéré que la sentence arbitrale rendue le 5 juin 2007 valait jugement sur l'action en libération de dette, ce qui permettait de mettre fin à la poursuite n° 03 116.062 A et, partant, de lever la saisie provisoire.
3.1 Lorsque le créancier a obtenu une mainlevée provisoire, le débiteur peut empêcher la continuation de la poursuite par l'introduction d'une action en libération de dette. Il dispose à cette fin d'un délai de vingt jours à compter de la mainlevée provisoire (cf. <ref-law>). Cette action doit lui permettre de démontrer l'inexistence ou l'inexigibilité de la créance invoquée par le créancier poursuivant (<ref-ruling> consid. 5a) au moment de la notification du commandement de payer (<ref-ruling> consid. 1; arrêt 5A_164/2008 du 9 septembre 2008 consid. 4.2.1 non publié de l'<ref-ruling>). Selon la jurisprudence du Tribunal fédéral, elle peut être intentée devant un Tribunal arbitral (<ref-ruling> consid. 2). Si l'action en libération de dette est admise, la poursuite est arrêtée définitivement; elle tombe, ce qui entraîne la caducité de la décision de mainlevée provisoire et de la saisie exécutée à titre provisoire (ATF 76 III 2 consid. 1 in fine; André Schmidt, Commentaire romand de la LP, 2005, n. 22 ad <ref-law>; PIERRE-ROBERT GILLIÉRON, op. cit., n. 118 ad <ref-law>; DANIEL STAHEHELIN, Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, I, 1998, n. 67 ad <ref-law>; DOMINIK VOCK, Kurzkommentar SchKG, 2009, n. 15 ad <ref-law>).
3.1 Lorsque le créancier a obtenu une mainlevée provisoire, le débiteur peut empêcher la continuation de la poursuite par l'introduction d'une action en libération de dette. Il dispose à cette fin d'un délai de vingt jours à compter de la mainlevée provisoire (cf. <ref-law>). Cette action doit lui permettre de démontrer l'inexistence ou l'inexigibilité de la créance invoquée par le créancier poursuivant (<ref-ruling> consid. 5a) au moment de la notification du commandement de payer (<ref-ruling> consid. 1; arrêt 5A_164/2008 du 9 septembre 2008 consid. 4.2.1 non publié de l'<ref-ruling>). Selon la jurisprudence du Tribunal fédéral, elle peut être intentée devant un Tribunal arbitral (<ref-ruling> consid. 2). Si l'action en libération de dette est admise, la poursuite est arrêtée définitivement; elle tombe, ce qui entraîne la caducité de la décision de mainlevée provisoire et de la saisie exécutée à titre provisoire (ATF 76 III 2 consid. 1 in fine; André Schmidt, Commentaire romand de la LP, 2005, n. 22 ad <ref-law>; PIERRE-ROBERT GILLIÉRON, op. cit., n. 118 ad <ref-law>; DANIEL STAHEHELIN, Kommentar zum Bundesgesetz über Schuldbetreibung und Konkurs, I, 1998, n. 67 ad <ref-law>; DOMINIK VOCK, Kurzkommentar SchKG, 2009, n. 15 ad <ref-law>).
3.2 3.2.1 En l'espèce, la poursuivie a saisi le Tribunal arbitral dans le délai de vingt jours de l'<ref-law> afin de faire constater l'inexistence de la créance déduite dans la poursuite 03 116.062 A (arrêt 7B.55/2006 du 21 septembre 2006 consid. 3.3). Par sa sentence du 5 juin 2007, le Tribunal arbitral a constaté que cette créance n'existait pas, faute de réalisation de la condition à laquelle était subordonnée l'efficacité du Protocole d'accord du 31 juillet 2002, à savoir l'identification de fonds saisis-arrêtés au Luxembourg. Dans l'Addendum du 17 octobre 2007, il a rejeté la demande en interprétation de la sentence formée par la recourante et confirmé que la créance déduite en poursuite était inexistante. Cette sentence a été reconnue (arrêt 4A_403/2008 du 9 décembre 2008), de sorte qu'elle bénéficie en Suisse de la force de chose jugée.
3.2.2 La recourante se méprend sur le sens de l'arrêt rendu le 21 septembre 2006 (arrêt 7B.55/2006 consid. 3.3). Le Tribunal fédéral n'y a pas jugé qu'il appartenait au Tribunal arbitral de décider si l'action ouverte devant lui valait action en libération de dette. Selon cet arrêt, le Tribunal arbitral devait décider si l'action en libération de dette ouverte satisfaisait aux exigences formelles de recevabilité prévues par le Règlement d'arbitrage de la CCI. De leur côté, les autorités de poursuite devaient attendre que le Tribunal arbitral déclare l'action en libération de dette irrecevable, ou alors statue sur le fond, ce qu'il a depuis lors fait par sentence du 5 juin 2007 admettant l'action en libération de dette.
3.2.3 Aux yeux de la recourante, le Tribunal arbitral n'a pas rendu un jugement définitif mais il a seulement constaté que la créance était inexistante "en l'état". Elle en conclut qu'elle a encore la possibilité de démontrer l'existence et l'exigibilité de la créance déduite en poursuite et elle soutient avoir introduit une nouvelle action devant un Tribunal arbitral à cette fin. Selon elle, en l'absence d'un jugement tranchant de manière définitive la question de l'existence et de l'exigibilité de la créance, l'Office ne pouvait mettre fin à la poursuite.
En l'occurrence, dans sa sentence du 5 juin 2007, le Tribunal arbitral a jugé que la créance était conditionnelle et que cette condition n'était pas avenue; il a donc constaté que la créance réclamée en poursuite était inexistante "en l'état", à savoir au moment où il a statué. A fortiori, la créance était donc inexistante au moment de la notification du commandement de payer. La question de l'existence et de l'exigibilité de la créance à ce moment-là a ainsi été tranchée de manière définitive, la recourante n'ayant pas attaqué cette sentence. En tant qu'elle se prévaut d'une nouvelle procédure arbitrale, force est de constater que l'existence d'une telle procédure, voire de nouvelles démarches, ne ressortent pas de l'arrêt attaqué et constituent donc des faits nouveaux dont il ne peut être tenu compte (<ref-law>). Il appartenait à la recourante de démontrer que dite procédure aurait pu avoir une influence sur la première sentence, qu'il ne se serait pas agi d'un fait nouveau et que le Tribunal fédéral aurait donc pu le prendre en considération. Cela étant, l'action en libération de dette admise "en l'état" n'exclut pas que la recourante, à supposer que la condition se réalise dans le futur - ce qui permettrait la naissance de la créance - , engage une nouvelle procédure d'exécution forcée à raison de la même créance (cf. <ref-ruling> consid. 5a; 79 II 284 consid. 4).
En conclusion, la poursuite objet de la présente procédure était prématurée. Le débiteur poursuivi ayant obtenu gain de cause dans l'action en libération de dette, l'office des poursuites ne pouvait que constater la caducité de la mainlevée provisoire et de la poursuite n° 03 116.062 A.
4. Au vu de ce qui précède, le recours doit être rejeté. Les frais seront mis à la charge de la recourante (<ref-law>). Elle versera en outre des dépens à l'intimée (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. La requête de suspension est sans objet.
2. Le recours est rejeté.
3. Les frais judiciaires, arrêtés à 20'000 fr., sont mis à la charge de la recourante.
4. Une indemnité de 20'000 fr. à payer à l'intimée à titre de dépens est mise à la charge de la recourante.
5. Le présent arrêt est communiqué aux parties et à la Commission de surveillance des offices des poursuites et des faillites du canton de Genève.
Lausanne, le 7 septembre 2010
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: La Greffière:
Hohl Rey-Mermet