Faits: A. Souffrant des séquelles d'une cardiopathie congénitale, M._, née en 1959, a bénéficié de différentes prestations de l'assurance-invalidité. Elle perçoit notamment une rente entière depuis le 1er novembre 1984 et a été mise au bénéfice d'une allocation pour impotence moyenne depuis le 1er novembre 1998. Au cours d'une procédure de révision, l'Office de l'assurance-invalidité du canton de Neuchâtel (ci-après: l'office AI) a confirmé le droit à la rente (communication du 10 avril 2006) et supprimé celui à l'allocation (décision du 8 novembre 2006). Contestée, la décision a été annulée par le Tribunal administratif du canton de Neuchâtel (jugement du 28 février 2007). L'administration a alors maintenu l'allocation, mais en a revu le montant en qualifiant désormais l'impotence de faible (décision du 25 juin 2008). B. L'assurée a déféré cette dernière décision au Tribunal administratif du canton de Neuchâtel. Elle concluait au maintien de son droit, estimant en substance que les circonstances qui avaient conduit à son octroi n'avaient pas subi de modifications significatives. La juridiction cantonale a accédé aux conclusions de l'intéressée, considérant en outre qu'il n'existait pas de motifs de reconsidération (jugement du 12 février 2009). C. L'office AI interjette un recours en matière de droit public contre ce jugement. Il en requiert l'annulation et conclut à la confirmation de la décision litigieuse ou à ce que la cause lui soit renvoyée pour compléter l'instruction. Il a aussi sollicité l'octroi de l'effet suspensif qui lui a été accordé par ordonnance du 10 juin 2009. M._ conclut au rejet du recours. Elle requiert également le bénéfice de l'assistance judiciaire. L'Office fédéral des assurances sociales propose d'admettre le recours. 