Faits: A. A.a. Le 31 mars 2010, l'Etat de Genève ( poursuivant ) a introduit une poursuite à l'encontre de A._ ( poursuivi ) en recouvrement des sommes de xxxx fr. et de xxxx fr., toutes deux avec intérêts à 5% dès le 18 février 2009. Le 20 avril 2010, l'Office des poursuites de Genève a établi un commandement de payer, qu'il a notifié le 6 mai 2010 au poursuivi ( poursuite n° xxxx ); le procès-verbal de notification figurant au verso de l'acte indique que le poursuivi a « pris connaissance » du commandement de payer, mais qu'il a « refusé [d'en] prendre possession », car il prétend être « domicilié en France » en un lieu connu du poursuivant. A.b. Après l'octroi de la mainlevée provisoire, le poursuivant a requis le 10 mars 2011 la continuation de la poursuite. Le 22 mars 2011, l'Office a expédié au poursuivi, sous plis simple et recommandé, un avis de saisie à son adresse à X._ (...); ces envois ont été retournés à l'expéditeur, avec la mention que le « destinataire est introuvable à l'adresse indiquée ». Le 17 juin 2011, l'Office a délivré au poursuivant un « procès-verbal de non-lieu de saisie », qui expose notamment ce qui suit: « Suite à un constat à ... - X._, il appert que le débiteur ne réside plus à cette adresse. A noter que les différents courriers envoyés à l'adresse énoncée ci-dessus, ont été retournés par la poste à l'Office avec la mention "le destinataire est introuvable à l'adresse indiquée". Dès lors, l'Office a procédé à diverses demandes bancaires, lesquelles se sont toutes révélées négatives. De plus, après vérifications auprès de l'Office cantonal de la population, il s'avère que le débiteur n'est plus résident à Genève depuis le 31.12.2004, la mention "quitté" est inscrite dans leur fichier (destination Y._, France). Pour toutes ces raisons, le présent non-lieu est établi ». Le 27 juin 2011, le poursuivant a requis l'Office de reconsidérer cette décision et de procéder à une nouvelle notification de l'avis de saisie, subsidiairement de délivrer un acte de défaut de biens. En cas de refus, il a demandé « de considérer la présente comme valant plainte 17 LP contre le procès-verbal de non-lieu de saisie », l'Office étant alors prié d'acheminer cette écriture à l'autorité compétente. A.c. Dans le cadre de la plainte qu'avait déposée un autre poursuivant à l'encontre d'un « procès-verbal de non-lieu de notification du commandement de payer » dressé par l'Office en raison de l'absence de for de poursuite à Genève, l'Autorité genevoise de surveillance des Offices des poursuites et faillites (ancienne dénomination de l'autorité cantonale de surveillance) a, par décision du 7 juillet 2011, annulé ladite mesure et invité l'Office à donner suite à la réquisition du poursuivant. L'autorité de surveillance a notamment admis l'existence d'éléments conduisant à admettre que le poursuivi n'avait pas déménagé d'une manière effective à Y._ (France), mais qu'il était resté domicilié à Genève. Cette décision n'a pas été déférée au Tribunal fédéral. Le 11 octobre 2012, la Chambre de surveillance des Offices des poursuites et faillites du canton de Genève a rejeté la plainte formée par le poursuivi dans le cadre d'une autre poursuite introduite contre lui par l'Etat de Genève ( n° xxxx ); l'autorité cantonale a constaté que le plaignant n'avait pas fourni d'indices nouveaux permettant de conclure qu'il était domicilié en France, de sorte qu'il y avait lieu de s'en tenir à la décision du 7 juillet 2011. Cette décision n'a pas davantage fait l'objet d'un recours au Tribunal fédéral. A.d. Le 7 septembre 2011, l'Office a transmis au mandataire genevois du poursuivi deux convocations destinées à celui-ci. Le 15 septembre 2011, l'avocat a informé l'Office que son client était domicilié en France; le 1er novembre 2011, il lui a transmis une attestation délivrée le 22 juin 2010 par la mairie, d'après laquelle le poursuivi est domicilié au lieudit «...» à Y._ (Ain) depuis janvier 2005. B. Le 21 février 2013, le conseil du poursuivant a prié l'Office de le tenir informé du suivi de la procédure et de lui transmettre le procès-verbal de saisie et/ou un acte de défaut de biens. L'Office lui a répondu, par courrier du 25 février 2013 (reçu le 1er mars), qu'un procès-verbal de non-lieu de saisie lui avait été adressé le 17 juin 2011 et lui en a remis une copie. Le 6 mars 2013, le poursuivant a porté plainte pour déni de justice; il a conclu à ce que le procès-verbal de non-lieu de saisie soit annulé et à ce qu'il soit ordonné à l'Office « de procéder aux saisies et démarches qui s'imposent, cas échéant délivrer un acte de défaut de bien ». Statuant le 18 avril 2013, la Chambre de surveillance des Offices des poursuites et faillites du canton de Genève a admis la plainte, annulé le procès-verbal de non-lieu de saisie et invité l'Office à donner suite à la réquisition de continuer la poursuite par la communication d'un avis de saisie au poursuivi. C. Par mémoire du 6 mai 2013, le poursuivi exerce un recours en matière civile au Tribunal fédéral; il conclut à la confirmation du procès-verbal de non-lieu de saisie. Des observations sur le fond n'ont pas été requises. Par ordonnance du 29 mai 2013, le Président de la IIe Cour de droit civil a attribué l'effet suspensif au recours. 