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.