Faits:
A. Suite à une information transmise le 21 février 2005 par le service vétérinaire cantonal neuchâtelois, une instruction douanière a été ouverte à l'encontre de X._. A l'issue de cette enquête, la Direction générale des douanes a infligé à cette dernière, par mandat de répression du 3 mai 2006, une amende de 10'000 fr. notamment pour infractions à la loi du 2 septembre 1999 régissant la taxe sur la valeur ajoutée, à la loi du 9 mars 1978 sur la protection des animaux et à la loi du 1er juillet 1966 sur les épizooties.
Il était reproché à X._ d'avoir exporté un total de quinze chiots, à quatre reprises, entre octobre 2003 et février 2005, afin de leur faire couper la queue en France, puis de les avoir réimportés en Suisse, sans annonce ni déclaration au passage de la frontière. La Direction générale des douanes a rendu un prononcé pénal, le 11 octobre 2006, rejetant l'opposition formée contre le mandat de répression et confirmant l'amende infligée à X._.
B. Par jugement du 2 octobre 2007, le Tribunal de police du district de la Chaux-de-Fonds, saisi à la demande de X._, a acquitté cette dernière au bénéfice d'une erreur sur l'illicéité.
Par arrêt du 4 novembre 2009, la Cour de cassation pénale du Tribunal cantonal de Neuchâtel a rejeté le pourvoi en cassation de l'Administration fédérale des douanes et a confirmé l'acquittement.
C. L'Administration fédérale des douanes interjette un recours en matière pénale au Tribunal fédéral. Elle conclut, principalement, à la condamnation de X._ pour infraction à la LPA, à une amende de 10'000 fr., et, subsidiairement, au renvoi de la cause à l'autorité inférieure pour nouveau jugement.
Le Ministère public de la Confédération, celui du canton de Neuchâtel et la Cour de cassation pénale du canton de Neuchâtel ont renoncé à déposer des observations. X._ conclut au rejet du recours avec suite de frais et dépens et oppose la prescription de l'action pénale.

Considérant en droit:
1. L'Administration fédérale des douanes a pris part à la procédure devant l'autorité précédente. Elle est « concernée » au sens de l'art. 81 al. 1 let. b ch. 7 LTF (cf. art. 32 al. 5 LPA). Elle est légitimée au recours.
2. Invoquant la violation du droit fédéral et l'arbitraire dans les constatations cantonales, la recourante estime que l'intimée s'est rendue coupable d'infraction à la LPA sans avoir été sous l'emprise de l'erreur sur l'illicéité.
2.1 Les faits litigieux ont cessé en février 2005. Ils ont été jugés au mois d'octobre 2007, soit avant l'entrée en vigueur, le 1er septembre 2008, de la nouvelle loi sur la protection des animaux (LPA; RS 455). L'autorité de recours neuchâteloise exerce essentiellement une compétence de cassation (v. arrêt 6B_3/2007 du 14 juin 2007, consid. 4.2), de sorte qu'elle n'est pas juge du fond. L'ancien droit (aLPA; RO 1981 562) demeure ainsi applicable même si cette autorité a statué après l'entrée en vigueur du nouveau droit (cf. <ref-ruling> consid. 15b p. 388). Le nouvel art. 28 al. 3 LPA n'est, au demeurant, pas plus favorable à X._ que l'art. 29 al. 2 aLPA, que ce soit sous l'angle des conditions de l'infraction ou des sanctions infligées. Commet une infraction au sens de cette norme, toute personne qui, intentionnellement ou par négligence, aura notamment contrevenu à l'interdiction d'importer des chiens ayant les oreilles et/ou la queue coupée (art. 78 al. 3 de l'ancienne ordonnance concernant l'importation, le transit et l'exportation d'animaux et de produits animaux [aOITE]; depuis le 1er septembre 2008: art. 22 al. 1 let. b de l'ordonnance sur la protection des animaux du 23 avril 2008 [OPAn; RS 455.1]).
2.2 Conformément à l'ancien <ref-law> (erreur de droit), la peine pouvait être atténuée librement par le juge à l'égard de celui qui avait commis un crime ou un délit alors qu'il avait des raisons suffisantes de se croire en droit d'agir. Le juge pouvait aussi exempter le prévenu de toute peine. L'erreur au sens de cette disposition visait celui qui agissait de manière intentionnelle et en connaissance de tous les faits, mais considérait à tort son comportement comme licite (<ref-ruling> consid. 3.1, p. 240). Depuis le 1er janvier 2007, le nouvel <ref-law> (erreur sur l'illicéité) dispose que quiconque ne sait ni ne peut savoir au moment d'agir que son comportement est illicite n'agit pas de manière coupable. Lorsque l'erreur est évitable, le juge atténue la peine. Cette atténuation n'est plus facultative, mais obligatoire (Message du Conseil fédéral du 21 septembre 1998, FF 1998 1787 ss, ch. 212.44, p. 1814; arrêt 6B_430/2007 du 17 mars 2008, consid. 5.5). L'<ref-law> est ainsi plus favorable (<ref-law>) à l'auteur que l'ancien droit en ce qui concerne les conséquences d'une erreur.
2.2.1 En l'espèce, le premier juge a retenu que l'intimée était légitimée à penser que la caudectomie, licite en France, n'était pas punissable en Suisse. Il a relevé, d'une part, que le Ministère public, dans une ordonnance de classement du 2 mars 2005, avait abouti à la même conclusion. X._ n'avait, d'autre part, pas vu son propre comportement comme celui d'une importatrice puis d'une exportatrice de marchandises et, bien que les chiens fussent visibles, personne ne lui avait jamais demandé quoi que ce soit à son passage à la douane (jugement, consid. 5, p. 4 s.).
La cour cantonale, statuant en cassation et se considérant liée par cet état de fait, a jugé qu'il ne ressortait pas de la décision de première instance que l'intimée avait agi d'une manière qu'elle savait interdite ou qu'elle aurait dû avoir des doutes sur ce point. En se référant, elle aussi, à l'ordonnance de classement du 2 mars 2005 et au comportement des douaniers, la cour cantonale a estimé que cela était de nature à conforter l'intimée dans l'idée que son comportement n'était pas illicite (arrêt entrepris, consid. 2c, p. 4).
2.2.2 Que l'intimée ait pu penser la caudectomie non punissable en Suisse est sans pertinence quant à l'erreur sur l'illicéité (<ref-ruling> consid. 2, p. 210). Cette constatation de fait est, en outre, en contradiction manifeste avec les pièces du dossier dont il ressort sans aucune ambiguïté que l'intimée savait pertinemment l'opération prohibée en Suisse (procès-verbal d'interrogatoire de X._ par l'Office des enquêtes de Neuchâtel de l'Administration fédérale des douanes, du 29 juin 2005, p. 2). Or, il n'est pas raisonnablement concevable que l'interdiction d'une telle mutilation ne soit pas assortie d'une sanction pénale. Du reste, il n'est pas reproché à l'intimée d'avoir procédé ou fait procéder à cette intervention en Suisse, mais d'y avoir importé des animaux préalablement opérés. Quant à l'ordonnance de classement du 2 mars 2005, qui est fondée sur le principe de la territorialité (<ref-law>), elle porte sur le seul reproche d'avoir fait opérer les chiens en France et non sur l'infraction consistant à importer des animaux caudectomisés. Elle est, de surcroît, postérieure aux faits reprochés à l'intimée et n'a donc, d'aucune manière, pu influencer la représentation juridique de cette dernière au moment où elle a agi. Enfin, la seule passivité des autorités douanières ne permet pas encore, à elle seule, de conclure à une erreur sur l'illicéité de l'auteur (<ref-ruling> consid. 2, p. 210). Au demeurant, en l'espèce, même si les chiens étaient visibles dans la voiture de l'intimée, rien n'indique que les douaniers les auraient effectivement vus et auraient constaté les mutilations. Il n'est donc pas établi que les autorités douanières ont fait preuve d'une tolérance susceptible d'induire l'intimée en erreur sur la licéité de son comportement. Ces considérations ne sauraient, en conséquence, fonder une erreur sur l'illicéité en relation avec le comportement reproché à l'intéressée.
2.2.3 Il s'agit plutôt de déterminer si cette dernière avait conscience d'agir de manière illicite en important en Suisse des animaux préalablement opérés à sa demande en France après y avoir été exportés à cette seule fin.
Les autorités cantonales ont certes retenu que, dans sa représentation, l'intimée n'avait pas appréhendé son propre comportement comme celui d'une exportatrice/importatrice. Cette appréciation ne suffit cependant pas à exclure tout sentiment d'illicéité quant aux agissements en cause. Tout d'abord, cette justification repose sur les seules affirmations de l'intimée selon lesquelles elle estimait n'avoir pas à déclarer à la douane des marchandises et prestations d'une valeur inférieure à la franchise douanière (jugement, loc. cit.). Elle n'a donc de sens qu'en ce qui concerne le prix de la prestation vétérinaire réalisée en France (8 euros par queue coupée), indépendamment des chiens eux-mêmes et de leur valeur, ce que l'intimée, qui exploite une fiduciaire et connaissait ses obligations en matière de déclaration douanière (procès-verbal précité, loc. cit.) ne pouvait méconnaître. Or, la recourante ne conclut pas à la condamnation de l'intimée en relation avec des infractions fiscales, mais uniquement en ce qui concerne l'importation de chiens caudectomisés à l'étranger. Il faut, en revanche, prendre en considération le but de la manoeuvre, qui visait exclusivement à contourner la législation suisse sur la protection des animaux. En effet, l'intimée savait, par son propre vétérinaire suisse, qui avait refusé d'y procéder, que la caudectomie était prohibée dans notre pays (v. supra consid. 2.2.2). Dans ces conditions, il n'est pas possible qu'elle n'ait pas éprouvé de sérieux doutes sur la licéité de son comportement puisqu'il s'agissait d'un biais tendant à éluder la réglementation suisse. On pouvait dès lors attendre de l'intéressée, notamment eu égard à ses compétences professionnelles, qu'elle se renseignât auprès de l'autorité compétente. Il convient de compléter en ce sens l'état de fait de la décision entreprise en application de l'<ref-law>. Cela exclut, tout au moins, que l'erreur fût inévitable au sens du nouvel <ref-law> et, partant, l'acquittement.
Il convient, dès lors, de renvoyer la cause à l'autorité précédente afin qu'elle constate la réalisation de l'infraction et qu'elle fixe la peine.
3. Dans son mémoire de réponse, l'intimée oppose une nouvelle fois la prescription de l'action pénale relative aux infractions à la LPA. Elle soutient qu'elle est soumise au délai de prescription de l'aLPA (2 ans; 5 ans sous la LPA) en vertu du principe de la lex mitior qui vaut également en matière de prescription (<ref-ruling> consid. 5.1 p. 51). Les actes répétés à quatre reprises entre octobre 2003 et février 2005 devraient, selon elle, être considérés comme indépendants les uns des autres à défaut d'unité d'action (<ref-ruling> consid. 2.4.4 et 2.4.5 p. 93/94).
Cette argumentation est vaine. Elle méconnaît l'ancien <ref-law> (en vigueur du 1er octobre 2002 au 31 décembre 2006; depuis le 1er janvier 2007: <ref-law>) qui double les délais de prescription jusqu'à l'adaptation des autres lois fédérales, prolongeant ainsi le délai de deux ans de l'art. 30 aLPA à quatre ans. Selon l'<ref-ruling> (consid. 9.4.4), le prononcé pénal (<ref-law>), qui succède au mandat de répression (<ref-law>), équivaut - sous l'angle de la prescription - à un jugement de première instance. La prescription a donc été interrompue lorsque la Direction générale des douanes a statué et rejeté l'opposition de X._ le 11 octobre 2006. A cette date, aucun des actes poursuivis n'était prescrit.
4. Vu l'issue de la procédure, il est statué sans frais. Il n'y a pas lieu d'allouer des dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'arrêt attaqué annulé.
2. La cause est renvoyée à l'autorité cantonale pour nouveau jugement dans le sens des considérants.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué aux parties et à la Cour de cassation pénale du Tribunal cantonal de Neuchâtel.
Lausanne, le 26 août 2010
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Le Greffier:
Favre Vallat