Faits :
A.
Donnant suite le 8 août 2017 à la réquisition présentée par la société B._ AG ( poursuivante), l'Office des poursuites de Genève a notifié à A._ ( poursuivi) un commandement de payer la somme de 39'830 fr.50, augmentée des intérêts de retard (2'765 fr.) et des frais (297 fr.50); cette poursuite se fonde sur deux actes de défaut de biens après saisie ( poursuite n° xx xxxxxx x).
Par lettre recommandée du 16 août 2017, le poursuivi a informé l'Office qu'il " form [ait] opposition totale " à ladite poursuite " pour non-retour à meilleur [e] fortune ". Le 18 août suivant, l'Office a remis à la poursuivante l'exemplaire du commandement de payer destiné au créancier, muni du tampon humide: " Exception de non-retour à meilleure fortune (art. 265 LP), pas d'opposition à la créance "; le même jour, il a transmis une copie de cet acte au Tribunal de première instance de Genève afin qu'il statue sur ce moyen.
Le 1er novembre 2017, le poursuivi s'est adressé audit Tribunal pour manifester son désaccord avec la poursuite introduite à son encontre, raison pour laquelle il avait, dans son courrier du 16 août 2017, formé opposition totale, " en sus du non-retour à meilleure fortune ".
B.
Par jugement du 4 décembre 2017, le Tribunal de première instance a déclaré irrecevable l'opposition; en bref, il a retenu qu'une opposition pour non-retour à meilleure fortune n'entre pas en ligne de compte si la créance en poursuite est constatée dans un acte de défaut de biens après saisie. Le 22 février 2018, il a confirmé à la poursuivante que sa partie adverse n'avait pas intenté d'action en constatation du non-retour à meilleure fortune. Le lendemain, l'intéressée a requis la continuation de la poursuite.
C.
Par pli du 6 mars 2018, reçu le 9 mars 2018, l'Office a adressé un avis de saisie au poursuivi, l'invitant à se présenter dans ses locaux afin de l'interroger sur sa situation patrimoniale. Le 12 mars 2018, le poursuivi a porté plainte contre cet acte, concluant à sa nullité, subsidiairement à son annulation.
Statuant le 16 août 2018, la Chambre de surveillance des Offices des poursuites et faillites de la Cour de justice du canton de Genève n'est pas entrée en matière en raison de la tardiveté de la plainte.
D.
Par mémoire expédié le 30 août 2018, le poursuivi exerce un recours en matière civile au Tribunal fédéral; il reprend les conclusions formulées dans sa plainte.
Invités à répondre, l'autorité précédente se réfère aux considérants de sa décision; l'Office renvoie aux déterminations qu'il a présentées en instance cantonale; la poursuivante conclut au rejet du recours.
E.
Par ordonnance présidentielle du 26 septembre 2018, l'effet suspensif a été attribué au recours.
Considérant en droit :
1.
1.1. Le présent recours a été déposé dans le délai légal (art. 100 al. 2 let. a LTF) contre une décision finale (art. 90 LTF; cf. ATF 133 III 350 consid. 1.2) rendue en matière de poursuite pour dettes (art. 72 al. 2 let. a LTF) par une autorité cantonale de surveillance ayant statué en dernière (unique) instance (art. 75 al. 1 LTF). Il est recevable quelle que soit la valeur litigieuse (art. 74 al. 2 let. c LTF). Le poursuivi, qui a pris part à la procédure devant l'autorité précédente et possède un intérêt digne de protection à la modification de la décision attaquée, a qualité pour recourir (art. 76 al. 1 LTF).
1.2. L'avis de saisie (art. 90 LTF) constitue une décision susceptible de plainte selon l'art. 17 LP (arrêt 5A_17/2018 du 4 juillet 2018 consid. 2.1 et les références), en sorte que le présent recours est recevable de ce chef ( cf. sur cette condition: ATF 142 III 643 consid. 3.1).
2.
2.1. En bref, l'autorité cantonale a considéré que la plainte était tardive au regard de l'art. 17 al. 2 LP, puisque le poursuivi a eu connaissance en automne 2017 déjà du refus de l'Office d'enregistrer son opposition à la prétention en poursuite et il ne l'a pas interpellé pour connaître les motifs du non-enregistrement de son opposition. Il n'a pas davantage porté plainte après que le Tribunal de première instance, par jugement du 4 décembre 2017, eut déclaré irrecevable son opposition pour non-retour à meilleure fortune. En attendant jusqu'au 9 mars 2018 pour se plaindre du refus de l'Office d'enregistrer son opposition à la créance, " le plaignant n'a donc pas respecté le délai légal de dix jours ".
2.2. Cette argumentation ne peut être suivie. D'après la jurisprudence, un acte de poursuite exécuté en dépit d'une opposition est nul au sens de l'art. 22 al. 1 LP (LORANDI, Betreibungsrechtliche Beschwerde und Nichtigkeit, 2000, n° 28 ad art. 22 LP et les arrêts cités); faute d'être fondé sur un commandement de payer exécutoire, un tel acte " heurte les principes fondamentaux de la poursuite pour dettes " (ATF 109 III 53 consid. 2b). Or, comme l'expose avec raison le recourant, l'autorité de surveillance doit constater la nullité d'un acte de poursuite même si la plainte est tardive (parmi d'autres: LORANDI, op. cit., n° 272 ad art. 17 et n° 129 ad art. 22 LP, avec les citations). Il incombait dès lors à la cour cantonale d'examiner la question de la portée de l'opposition formée le 16 août 2017, d'autant que l'intéressé a explicitement invoqué dans sa plainte la nullité de l'avis de saisie, notifié " alors même qu'opposition a été faite à la créance et n'a pas été écartée " ( p. 6, ch. 33); cet examen fait défaut en l'occurrence, les juges précédents ayant focalisé tout leur raisonnement sur le " non-enregistrement " par l'Office de l'opposition à la créance en poursuite. Enfin, peu importe de savoir si l'opposition se rapportait ou non aussi au retour à meilleure fortune. Il est vrai qu'une telle opposition n'est pas ouverte lorsque la créance est constatée par un acte de défaut de biens après saisie (arrêt 5A_167/2010 du 27 avril 2010 consid. 2.1 et les références), mais cette problématique ressortit à la compétence exclusive du juge (ATF 130 III 678 consid. 2.1; 124 III 379 consid. 3b, avec les citations); cela ne dispense pas l'autorité de surveillance de rechercher si, au-delà des termes utilisés, l'opposition ne se réfère pas pour le moins à la créance.
2.3. L'autorité précédente n'étant pas entrée en matière sur la plainte, il y a lieu de lui renvoyer l'affaire afin de ne pas frustrer les parties d'un degré de juridiction sur l'application de la question litigieuse (ATF 144 II 184 consid. 1.1; 138 III 46 consid. 1.2 et la jurisprudence citée).
A toutes fins utiles, il convient néanmoins de préciser que le recourant ne saurait tirer avantage du principe " in dubio pro debitore ". Certes, le Tribunal fédéral s'est longtemps fondé sur ce principe pour interpréter la déclaration d'opposition ( cf. arrêt 5A_846/2012 du 4 novembre 2013 consid. 6.2.1 et les arrêts cités, in SJ 2014 I 109); récemment, il s'est cependant écarté de cette pratique, retenant que l'interprétation devait s'effectuer conformément au principe de la confiance (ATF 140 III 567 consid. 2.3; arrêt 5A_351/2016 du 19 juillet 2016 consid. 8).
3.
En conclusion, le présent recours doit être admis, la décision attaquée annulée et l'affaire renvoyée à l'autorité précédente pour qu'elle statue à nouveau dans le sens des considérants (art. 107 al. 2 LTF).
L'intimée succombe entièrement (ATF 141 V 281 consid. 11.1; 127 V 210 consid. 7.1 et les références), en sorte qu'il y a lieu de mettre à sa charge les frais et dépens de la procédure fédérale (art. 66 al. 1 et 68 al. 1 LTF).
Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, la décision attaquée est annulée et la cause est renvoyée à l'autorité précédente pour nouvelle décision.
2.
Sont mis à la charge de l'intimée:
2.1. les frais judiciaires, arrêtés à 1'500 fr.;
2.2. une indemnité de 2'000 fr. à payer au recourant à titre de dépens.
3.
Le présent arrêt est communiqué aux parties, à l'Office des poursuites de Genève et à la Chambre de surveillance des Offices des poursuites et faillites de la Cour de justice du canton de Genève.
Lausanne, le 23 janvier 2019
Au nom de la IIe Cour de droit civil
du Tribunal fédéral suisse
Le Président : Herrmann
Le Greffier : Braconi