Faits:
A. A.a Statuant sur la réquisition de Y._ SA, le Tribunal de première instance de Genève a ordonné le 18 août 2008 le séquestre, à hauteur de 11'207 fr. 65 plus intérêts, des avoirs de X._ auprès de la Banque Z._ SA; ce séquestre a été exécuté le lendemain par l'Office des poursuites de Genève (ci-après: l'Office) en mains de ladite banque; le procès-verbal de séquestre a été communiqué à la créancière le 29 août 2008.
Le séquestre a été validé par une poursuite (n° xxxx), dont la réquisition, déposée le 9 septembre 2008, mentionne que le poursuivi réside en Israël.
A.b Le 22 septembre suivant, la poursuivante a informé l'Office que, d'après les informations obtenues de l'Ambassade d'Israël, le poursuivi aurait été domicilié en Israël du 1er novembre 2006 au mois de janvier 2008, date à laquelle il aurait quitté ce pays; les recherches entreprises par la poursuivante pour retrouver l'intéressé sont restées vaines.
Le 15 octobre 2008, l'Office a tenté de notifier le commandement de payer à l'ancienne adresse du poursuivi mais sans succès.
La poursuivante ayant requis l'Office de notifier le commandement de payer par voie édictale, cette notification a eu lieu par publication dans la FAO et la FOSC du 29 octobre 2008; le commandement de payer n'a pas été frappé d'opposition.
Le 9 décembre 2008, la poursuivante a sollicité la continuation de la poursuite, afin que l'Office procède à la conversion du séquestre.
B. Le 17 février 2009, le poursuivi a porté plainte contre l'avis de conversion de séquestre du 2 février 2009, en reprochant à l'Office d'avoir procédé à la notification du commandement de payer par voie édictale, alors que son adresse était parfaitement connue; il a conclu à la nullité de la notification par voie édictale et, partant, à l'annulation de l'avis de conversion de séquestre, subsidiairement à la restitution du délai pour former opposition.
Dans son rapport du 11 mars 2009, l'Office a conclu au rejet de cette plainte.
Par décision du 23 avril 2009, la Commission de surveillance des offices des poursuites et des faillites du canton de Genève a débouté le plaignant.
C. Le plaignant interjette un recours en matière civile au Tribunal fédéral contre cette décision; il reprend les conclusions formulées en instance cantonale.
Des déterminations sur le fond n'ont pas été requises.
D. Par ordonnance du 6 juillet 2009, la Juge instructeur de la IIe Cour de droit civil a attribué l'effet suspensif au recours.

Considérant en droit:
1. 1.1 Déposé en temps utile (<ref-law>) contre une décision finale (<ref-law>; <ref-ruling> consid. 1.2 p. 351) prise en matière de poursuite pour dettes (<ref-law>) par une autorité de surveillance statuant en dernière (unique) instance cantonale (<ref-law> et 13 LP), le présent recours en matière civile est recevable, indépendamment de la valeur litigieuse (art. 74 al. 2 let. c LTF).
1.2 La mesure de l'Office critiquée - avis de conversion d'un séquestre en saisie - n'a pas pour objet une «mesure provisionnelle» au sens de l'<ref-law>; les griefs recevables ne sont dès lors pas restreints à la violation des droits constitutionnels (arrêt 5A_638/2008 du 5 décembre 2008 consid. 2).
1.3 La plainte pénale déposée le 24 avril 2009 en mains du Procureur général du canton de Genève, à savoir postérieurement à la décision entreprise, constitue un vrai novum, qui est d'emblée irrecevable (<ref-ruling> consid. 2.1 p. 343/344).
2. Invoquant l'<ref-law>, le recourant se réfère à plusieurs pièces qui visent à confirmer qu'il a toujours résidé en Israël; il se plaint à cet égard d'un état de fait arbitrairement lacunaire.
Un tel procédé n'est pas admissible. Il appartient au recourant d'établir d'une manière circonstanciée en quoi les conditions posées par la disposition précitée seraient remplies, étant souligné, par surcroît, que la faculté de compléter ou rectifier d'office les constatations de fait n'entre en considération que si l'inexactitude saute aux yeux (<ref-ruling> consid. 1.4.3 p. 254/255; <ref-ruling> consid. 6.2 p. 288). Or, en l'occurrence, le recourant ne prétend même pas avoir (régulièrement) produit en instance cantonale les pièces dont il se prévaut; au surplus, il se borne à exposer sa propre version des faits, sans nullement démontrer en quoi les constatations de l'autorité de surveillance seraient manifestement inexactes (<ref-law>), à savoir arbitraires au sens de l'art. 9 Cst. (<ref-ruling> consid. 1.2.2 p. 252 et 384 consid. 4.2.2 p. 391). En définitive, il n'y a pas lieu de s'écarter du principe posé par l'<ref-law>.
3. Lorsque le débiteur demeure à l'étranger, il est procédé à la notification par l'intermédiaire des autorités de sa résidence (<ref-law>). S'il existe un traité international - en l'espèce la Convention de La Haye du 15 novembre 1965 relative à la signification et à la notification à l'étranger des actes judiciaires et extrajudiciaires en matière civile ou commerciale -, l'office des poursuites doit se conformer à ses dispositions (<ref-ruling> consid. 2a p. 396). La notification s'effectue par publication lorsque, notamment, le débiteur n'a pas de domicile connu (<ref-law>). Selon la jurisprudence, la notification du commandement de payer par voie édictale constitue un ultime moyen; il ne faut y recourir que lorsque toutes les recherches basées sur la situation de fait ont été entreprises par le créancier et l'office des poursuites pour découvrir une éventuelle adresse de notification du débiteur (<ref-ruling> consid. 2a in fine p. 62 et les références; cf., dans le même sens, pour l'<ref-law>: <ref-ruling> consid. 4 p. 558 et la doctrine citée). Le débiteur est en droit de demander l'annulation d'une notification opérée en violation de ces principes, même s'il a pris connaissance de l'acte mal notifié et qu'il a pu sauvegarder ses droits en formant opposition (<ref-ruling> consid. 1 p. 466/467).
3.1 En l'occurrence, l'autorité de surveillance a retenu que l'instruction du dossier avait permis de constater que le poursuivi avait bien quitté la Suisse pour Israël le 1er novembre 2006; toutefois, selon les renseignements obtenus par la créancière auprès de l'Ambassade de Suisse à Tel Aviv, il était «annoncé comme ayant quitté Israël pour retourner en Suisse le 3 mai 2007, sans indiquer de nouvelle adresse». De plus, l'Office a précisé que, dans le cadre d'une autre poursuite, il lui avait notifié avec succès un commandement de payer à son adresse à Genève; en revanche, la notification tentée le 15 octobre 2008 à la même adresse s'était soldée par un échec. Partant, la juridiction précédente a conclu que, malgré les recherches de la poursuivante, démontrées par pièces, l'adresse du poursuivi était inconnue, de sorte que la notification par voie édictale apparaissait régulière.
3.2 Quoi qu'en dise le recourant, l'Office et la poursuivante pouvaient se fier aux renseignements délivrés par l'Ambassade d'Israël à Berne, c'est-à-dire la représentation officielle de l'Etat dans lequel le poursuivi prétend résider depuis le 1er novembre 2006. De toute manière, ces renseignements ont été confirmés, mais avec une date de départ différente (3 mai 2007), par l'Ambassade de Suisse en Israël. L'allégation du recourant selon laquelle celle-ci n'aurait été interpellée qu'après la notification par voie édictale ne ressort pas des faits constatés par les juges précédents; elle ne saurait dès lors être prise en compte (<ref-law>; cf. supra, consid. 2).
L'autorité précédente s'est également fondée sur la circonstance que l'Office avait tenté de notifier sans succès le commandement de payer à l'adresse du débiteur à Genève, ce qu'il était pourtant parvenu à faire (en juin 2008; <ref-law>) dans le cadre d'une autre poursuite. A cet égard, il ressort des constatations de la décision entreprise que la poursuivante a procédé encore à plusieurs démarches pour déterminer si le poursuivi avait une adresse à Genève ou en Suisse. Or, le recourant ne critique pas le motif supplémentaire tiré de l'absence d'un domicile connu en Suisse (cf. <ref-ruling>), ni ne démontre que ces constatations seraient arbitraires (cf. supra, consid. 2).
En considérant, sur la base des éléments précités, que le recourant n'avait pas de domicile connu et, partant, en confirmant la régularité de la notification litigieuse, l'autorité précédente n'a, dès lors, pas violé le droit fédéral.
4. En conclusion, le présent recours doit être rejeté dans l'étroite mesure de sa recevabilité, aux frais du recourant (<ref-law>). L'intimée n'étant pas représentée par un avocat (<ref-law>; <ref-ruling>), elle ne saurait prétendre à des dépens pour ses déterminations sur la requête d'effet suspensif (<ref-ruling> consid. 4 p. 446).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
3. Il n'est pas alloué de dépens à l'intimée.
4. 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 10 juillet 2009
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Le Greffier:
Hohl Braconi