Faits:
A. P._, née en 1963, sans formation professionnelle particulière, a travaillé en qualité d'ouvrière d'horlogerie d'octobre 1992 à mars 1998, puis dès juin 2000 en tant que caissière à mi-temps au service de X._.
Le 31 janvier 2000, elle s'est annoncée à l'assurance-invalidité. Dans un avis médical du 17 août 2000, le docteur T._, médecin AI, a relevé que les diagnostics d'état anxio-dépressif, de fibromyalgie et d'obésité était connus depuis environ dix ans. Il a requis la mise en oeuvre de tests projectifs avec bilan psychologique, qui ont été confiés à E._, psychologue. Dans son rapport du 14 septembre 2000, la prénommée a indiqué que le travail de caissière semblait idéal, activité dans laquelle la capacité de travail était limitée à 50 %, susceptible de s'aggraver. Le 28 novembre 2000, le docteur T._ a ajouté le diagnostic de séquelles de psychose infantile (QIg 65) avec tendances projectives; les renseignements médicaux étaient suffisants et une incapacité de travail de 50 % dans une activité adaptée devait être admise. Quant au docteur S._, il a confirmé, dans un rapport du 17 juillet 2001, les diagnostics de phobie sociale, d'état dépressif important, de fibromyalgie, d'obésité et de troubles psychiques chroniques depuis février 2000; à son avis, la capacité de travail restait de 50 %. Par décision du 16 octobre 2001, l'Office cantonal AI du Valais (l'office AI) a mis l'assurée au bénéfice d'une demi-rente d'invalidité depuis le 1er août 2001, fondée sur un degré d'invalidité de 55 %. Le droit à la rente a été confirmé en procédure de révision (communications des 16 octobre 2003 et 6 avril 2004).
Le 20 juillet 2004, invoquant une aggravation de son état de santé, P._ a requis la révision de son droit à la rente. Dans le cadre de cette procédure, l'office AI a recueilli plusieurs avis médicaux, singulièrement celui du SMR qui a mené un examen rhumatopsychiatrique (rapports des docteurs H._, spécialiste en psychiatrie et psychothérapie, et B._, spécialiste en médecine physique et réadaptation, du 27 avril 2005). Dans le rapport final du SMR du 3 mai 2005, le docteur A._ a retenu le diagnostic principal d'état dépressif moyen, associé à une fibromyalgie et une obésité, entraînant une incapacité de travail 50 % dans l'activité habituelle et dans un travail adapté.
Le droit de l'assurée à des mesures d'ordre professionnel a été nié par décision du 14 juillet 2005, laquelle n'a pas été contestée. Par décision du 15 juillet 2005, l'office AI a fixé le taux d'invalidité à 54 % et a maintenu le droit à la demi-rente. P._ s'est opposée à cette décision. Le 17 août 2005, l'office AI a informé l'assurée qu'il avait maintenu à tort le droit à la demi-rente, compte tenu du dossier et de la jurisprudence rendue en matière de fibromyalgie, et qu'il envisageait de réformer sa décision en supprimant la rente. L'assurée a retiré son opposition.
Par décision du 19 octobre 2005, confirmée sur opposition le 12 décembre 2005, l'office AI a supprimé, par voie de reconsidération, la demi-rente à compter du 1er décembre 2005, au motif que la décision du 16 octobre 2001 était manifestement erronée. Selon l'administration, la décision initiale avait été rendue sur la base d'une instruction médicale largement insuffisante, car l'avis d'un psychiatre n'avait pas été requis quand bien même l'assurée présentait des troubles somatoformes douloureux. Compte tenu du diagnostic d'état dépressif moyen qui avait été posé, l'office AI a nié l'existence d'une comorbidité psychiatrique autonome, tout comme il a exclu la présence de circonstances exceptionnelles qui auraient permis d'admettre que l'intimée n'aurait pas été en mesure de surmonter ses douleurs. D'après l'administration, on pouvait exiger de l'assurée qu'elle s'investisse dans une activité professionnelle à plein temps et son degré d'invalidité était ainsi de 2 %. L'office AI a retiré l'effet suspensif à un éventuel recours.
B. P._ a déféré cette décision au Tribunal des assurances du canton du Valais en concluant à son annulation et à la mise en oeuvre d'une expertise. Une requête de restitution de l'effet suspensif au recours a été rejetée par décision présidentielle du 13 février 2006.
Par jugement du 27 octobre 2006, la juridiction cantonale a admis le recours et annulé la décision sur opposition du 12 décembre 2005.
C. L'office AI a interjeté un recours de droit administratif contre ce jugement dont il a demandé l'annulation, avec suite de frais, en concluant à la confirmation de sa décision sur opposition du 12 décembre 2005.
L'intimée a conclu au rejet du recours, avec suite de frais et dépens. Elle a sollicité le bénéfice de l'assistance judiciaire pour la procédure fédérale.
Quant à l'Office fédéral des assurances sociales (OFAS), il s'en est remis à l'appréciation de la Cour de céans, à l'issue d'un préavis circonstancié.
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 (art. 132 al. 1 LTF; ATF 132 V 393 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. Le litige porte sur la suppression de la demi-rente d'invalidité, avec effet au 1er décembre 2005, par reconsidération de la décision du 16 octobre 2001.
4. Les premiers juges ont exposé correctement les règles légales et jurisprudentielles régissant les conditions de la reconsidération de décisions passées en force (cf. art. 53 al. 1 et 2 LPGA; ATF 127 V 466 consid. 2c p. 469). Par ailleurs, ils ont rappelé les principes développés par la jurisprudence en matière de troubles somatoformes douloureux (ATF 130 V 352; voir aussi ATF 130 V 396, 131 V 49 et 132 V 65), en particulier la nécessité de disposer d'une expertise psychiatrique lorsqu'il s'agit de se prononcer sur le caractère invalidant d'une telle affection psychique. Il suffit dès lors de renvoyer au consid. 2 du jugement attaqué.
5. Le Tribunal cantonal des assurances a constaté que le docteur Van Saanen, médecin traitant de l'intimée depuis 1991, avait fait état, notamment, de fibromyalgie accompagnant d'importants troubles psychiques, savoir une phobie sociale associée à une importante dépression, la capacité de travail étant alors de 50 %. E._, psychologue jadis mandatée par l'office AI, avait de son côté pratiqué des tests projectifs approfondis qui avaient mis en évidence des séquelles de psychose infantile et une efficience intellectuelle dysharmonique, l'intimée se situant dans la zone de débilité légère (QI 65); elle a aussi fait état d'une personnalité comportant des carences psychotiques de la représentation et un colmatage par des défenses de caractère, ajoutant que les interactions sociales étaient systématiquement interprétées sur le mode victime-persécuteur. Par ailleurs, le docteur T._ avait corroboré les appréciations du docteur S._ et de la psychologue E._. La juridiction cantonale a aussi constaté que durant de nombreuses années ces avis médicaux et psychologiques concordants n'avaient jamais été mis en doute, mais qu'ils avaient au contraire été corroborés par la plupart des médecins consultés en 2003 et 2004 (rapports des docteurs L._, D._ et O._). Enfin, le Tribunal des assurances a constaté que les experts du SMR, dans l'expertise rhumatopsychiatrique qu'ils avaient rendue en 2005, ne s'étaient nullement prononcés sur l'état de santé de l'intimée en 2001, en particulier sur la gravité de l'état anxio-dépressif tel qu'il prévalait à cette époque-là. De plus, le SMR n'avait apporté aucun élément permettant de démontrer que l'appréciation opérée en 2001 était erronée.
Selon les premiers juges, on ne pouvait dès lors pas admettre que l'appréciation concordante de la situation médicale et en particulier celle de l'évaluation de la capacité de travail, en 2001, était à ce moment-là lacunaire au point que la décision de rente doive être aujourd'hui tenue pour manifestement erronée. La juridiction cantonale a même constaté que les autres critères posés par la jurisprudence en matière de troubles somatoformes étaient réalisés de sorte que, pour ce motif également, le recourant ne pouvait supprimer la demi-rente accordée en 2001.
6. L'office recourant soutient que la décision de rente du 16 octobre 2001 était manifestement erronée en raison du caractère lacunaire de l'instruction de la demande de prestations. En particulier, l'administration met en exergue l'absence d'investigations psychiatriques de l'intimée, que la doctoresse C._, psychiatre traitante, avait pourtant recommandées à l'époque. Il rappelle que les examens psychologiques qui ont été réalisés en 2000 ne sont pas des pièces médicales et qu'ils ne sauraient, à eux seuls, constituer un moyen de preuve valable s'ils ne sont pas repris et intégrés dans un rapport ou une expertise psychiatrique. Selon le recourant, il était dès lors impossible, en l'état du dossier constitué en 2001, de se prononcer sur l'incapacité de travail pouvant découler des troubles psychiques dont souffrait l'intimée.
7. Dans son préavis, l'OFAS s'est déterminé sur le point de savoir si une décision initiale de rente doit être considérée comme manifestement erronée pour le seul motif que le caractère invalidant de troubles psychiques a été reconnu sans l'apport d'une expertise psychiatrique.
Dans le cas d'espèce, l'autorité fédérale de surveillance constate que l'octroi de la demi-rente a été précédé d'une instruction médicale d'une certaine envergure, même s'il faut déplorer l'absence d'une expertise psychiatrique. A son avis, la décision initiale correspondait à la situation réelle de l'assurée. L'OFAS en déduit que la décision initiale du 16 octobre 2001 n'était pas manifestement erronée.
8. En l'occurrence, il convient d'admettre, avec le Tribunal des assurances et l'OFAS, que l'instruction de la demande initiale de prestations a été lacunaire. En effet, au moment où l'administration a rendu sa décision de rente du 16 octobre 2001, elle ne disposait pas de l'avis d'un psychiatre (cf. ATF 130 V 396 consid. 5.3 et 6 pp. 398 ss), lequel était en principe nécessaire dès lors qu'il s'agissait de se prononcer sur l'incapacité de travail que le trouble somatoforme douloureux était susceptible d'entraîner chez l'intimée (cf. ATF 130 V 352 consid. 2.2.2 p. 353).
Nonobstant cette carence de l'instruction du dossier médical, on ne saurait pour autant en déduire que l'octroi d'une demi-rente d'invalidité était, pour ce seul motif, manifestement erroné en 2001. En effet, suivant les faits constatés par les premiers juges, l'intimée présentait d'importants troubles psychiques (singulièrement une phobie sociale associée à une importante dépression) et ne disposait, selon les docteurs S._ et T._ qui s'étaient exprimés à cette époque-là, que d'une capacité de travail de 50 %. Sans tenir compte des tests pratiqués par la psychologue E._ ni aborder la question de leur valeur probante, le dossier médical constitué en 2001 plaidait ainsi plutôt en faveur de l'octroi d'une demi-rente d'invalidité. En d'autres termes, on se trouve dans l'éventualité où une inexactitude manifeste ne saurait être admise dès lors que la décision d'octroi de la demi-rente, en 2001, paraissait admissible compte tenu de la situation de fait et de droit prévalant à cette époque (cf. arrêt B. du 19 décembre 2002, I 222/02, consid. 3.2, et les références).
Il s'ensuit que la décision portant suppression de cette prestation, par voie de reconsidération, était infondée, si bien que le recours de l'office AI sera rejeté.
9. La procédure n'est pas gratuite (art. 134 OJ, 2e phrase). Le recourant, qui succombe, en supportera les frais (art. 156 al. 1 OJ).
Pour le même motif, le recourant est redevable d'une indemnité de dépens à l'intimée (art. 159 al. 1 OJ), dont la demande d'assistance judiciaire n'a dès lors plus d'objet.
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours de droit administratif est rejeté.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimée une indemnité de dépens de 2'500 fr. (y compris la taxe à la valeur ajoutée).
4. Le présent arrêt est communiqué aux parties, au Tribunal des assurances du canton du Valais et à l'Office fédéral des assurances sociales.
Lucerne, le 29 février 2008
Au nom de la IIe Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Meyer Berthoud