Faits: A. Par ordonnance de mesures provisoires du 28 janvier 2000, le président du Tribunal civil du district du Val-de-Travers a condamné C.B._ à verser à A.B._, dès le 1er décembre 1999, une contribution d'entretien de 900 fr. par mois, et a ordonné à l'employeur de l'époux, l'entreprise Z._ Ltd, représentée par X._, d'effectuer une retenue de 900 fr. par mois sur le salaire du mari et de virer ce montant à l'épouse. C.B._ a formé, contre cette ordonnance, une opposition qui a été rejetée, puis un recours qui a été classé, de sorte que cette décision n'a jamais cessé d'être exécutoire. B. Par jugement du 23 mai 2003, le Tribunal de police du district du Val-de-Travers a condamné C.B._, pour violation d'une obligation d'entretien du 1er décembre 1999 au 24 février 2003, à trois mois d'emprisonnement et, par défaut, X._, pour complicité de violation d'une obligation d'entretien, à deux mois d'emprisonnement, peine complémentaire à celles prononcées les 21 mai 2001 et 18 mars 2002. C. Par arrêt du 20 juin 2005, la Cour de cassation pénale du Tribunal cantonal neuchâtelois a rejeté le pourvoi de C.B._ et admis partiellement celui de X._ en ce sens qu'elle a réduit sa peine à un mois d'emprisonnement. En bref, elle a jugé que X._ avait organisé, par le truchement d'une société domiciliée à l'étranger, un système dans lequel l'exécution forcée de l'obligation d'entretien devenait extrêmement difficile, qu'il s'était associé, de manière bien plus étroite qu'un employeur ordinaire, à la réalisation du délit et qu'il avait bien voulu ou, à tout le moins, accepté, le risque que la crédirentière ne reçût pas sa pension. En revanche, contrairement à l'autorité de première instance, la Cour de cassation a estimé que X._ n'avait pu se rendre coupable de complicité au-delà du 31 mars 2001, date correspondant à la fin du contrat de travail liant Z._ Ltd à C.B._, l'avis au débiteur contenu dans l'ordonnance de mesures provisionnelles ne s'étendant pas à tout employeur futur. Elle a aussi retenu que la plainte pénale déposée en septembre 2002 n'était pas tardive, puisque l'intimée ne savait pas ou ne pouvait savoir que le recourant n'était plus tenu, depuis le 1er avril 2001, de retenir chaque mois 900 fr. sur le salaire de son employé. D. X._ dépose un pourvoi au Tribunal fédéral, concluant à la nullité de l'arrêt attaqué. Il conteste sa qualité de complice, se plaint d'une violation des art. 69 ss ORC et invoque la péremption de la plainte pénale. Invités à se déterminer, la Cour de cassation pénale et le Ministère public neuchâtelois ont renoncé à formuler des observations, la première se référant à son arrêt, le second concluant au rejet du recours. L'intimée a conclu, principalement, à l'irrecevabilité du pourvoi et, subsidiairement, à son rejet.