Faits:
A. Par jugement du 7 avril 2009, le Tribunal correctionnel de l'arrondissement de Lausanne a condamné X._, pour actes d'ordre sexuel avec des enfants et enlèvement de mineur.
B. Saisie d'un recours du condamné, la Cour de cassation pénale du Tribunal cantonal vaudois l'a rejeté, le 12 juin 2009. Il ressort de cet arrêt les faits pertinents suivants.
B.a X._, né le ***1958, a fait la connaissance de A._, née le ***1988, au mois de juillet 2002, par le biais d'une petite annonce de presse, à laquelle la jeune fille a répondu par SMS. Après des échanges de ce type et des appels téléphoniques, ils se sont rencontrés une première fois à Lausanne, au mois d'août 2002. Des relations amicales se sont nouées. Ils ont commencé à se voir régulièrement dans des lieux publics, à Lausanne. Dans le courant du mois de septembre 2002, ils ont entretenu leurs premières relations sexuelles. Le 27 septembre 2002, A._ a appelé X._ par téléphone pour lui annoncer qu'elle voulait quitter le domicile familial en raison notamment des problèmes qu'elle rencontrait avec sa mère. Elle a menacé d'attenter à ses jours s'il ne venait pas la chercher. Le lendemain, vers 3h00, elle a quitté son domicile pour suivre X._.
B.b Entre le 20 septembre et le 2 novembre 2002, dans les régions de Vevey, Lausanne, Annemasse et Annecy, notamment, A._ et X._ ont entretenu à diverses reprises des relations sexuelles dans des chambres d'hôtel. Après avoir passé une première nuit au domicile de X._, A._ lui a fait savoir qu'elle ne voulait pas demeurer en Suisse, par crainte d'être inquiétée par la police. Ils se sont alors rendus dans la région de F._ pour y chercher un appartement et se sont finalement installés à B._, le 1er octobre 2002. Ils y ont été interpellés le 2 novembre suivant.
Les parents de A._, qui ignoraient où elle se trouvait, ont déposé plainte.
C. X._ forme un recours en matière pénale contre cet arrêt. Il conclut principalement à sa réforme en ce sens qu'il soit acquitté des chefs d'accusation d'actes d'ordre sexuel avec des enfants et d'enlèvement de mineur, les différents chiffres du jugement de première instance relatifs à la peine, aux précédents sursis et aux suites civiles étant rapportés et les frais laissés à la charge de l'Etat. A titre subsidiaire, il conclut à l'annulation de la décision querellée et au renvoi de la cause à l'autorité cantonale pour nouvelle décision au sens des considérants.
Invités à déposer des observations sur le recours, l'application de l'art. 220 CP en particulier, l'autorité cantonale s'est référée au considérant 5 de son arrêt, cependant que le Ministère public vaudois n'a pas donné de suite dans le délai imparti.

Considérant en droit:
1. Le recourant soulève tout d'abord un moyen de forme. Invoquant les art. 29 à 32 Cst., ainsi que les art. 6 et 13 CEDH, l'art. 6 par. 1 en particulier, il estime n'avoir pas bénéficié d'un procès équitable au regard de la garantie de l'égalité des armes. Le recourant rappelle qu'aux termes de l'art. 366, en corrélation avec l'art. 365 CPP/VD, les juges participant aux opérations postérieures à la clôture des débats doivent avoir assisté à toutes les opérations antérieures dès l'ouverture de ces derniers. Il relève que la composition du tribunal correctionnel a entièrement changé, après deux premières audiences des 12 avril et 15 septembre 2005, lors de la reprise de cause du 4 avril 2009. Deux témoins (C._ et D._) n'auraient pas été réentendus.
1.1 Le recourant s'est présenté à chacune des trois audiences. Il ne pouvait ignorer que le président, les juges et le greffier présents le 4 avril 2009 n'étaient pas ceux devant lesquels il avait comparu les 12 avril et 15 septembre 2005. Bien qu'assisté du même conseil à ces trois occasions, il n'a formulé aucune réquisition d'entrée de cause, pas plus qu'il n'a requis, dans le délai préalablement imparti avant l'audience (art. 320 CPP/VD) ou lors de celle-ci, une nouvelle audition du témoin D._. Le recourant n'a donc pas fait valoir ces moyens devant un juge qui aurait, le cas échéant, été en mesure de réparer les conséquences d'un éventuel vice. Il n'a pas satisfait à ses devoirs découlant du principe de la bonne foi en procédure (art. 5 al. 3 Cst.). Il doit, en conséquence, être déchu du droit de s'en prévaloir devant le Tribunal fédéral (<ref-ruling> consid. 1b i.f. p. 230; <ref-ruling> consid. 2a p. 495). Le grief est irrecevable dans cette mesure.
1.2 Au demeurant, comme l'a relevé à juste titre l'autorité cantonale, bien que, formellement, la cause n'ait été que « reprise » le 4 avril 2009, l'instruction a, en réalité, été renouvelée ab ovo. Il ressort en effet du procès-verbal du jugement de première instance qu'à cette occasion le président a donné lecture des principales pièces du dossier (cf. art. 341 al. 1 CPP/VD), notamment de l'ordonnance de renvoi, puis a interrogé l'accusé, le plaignant et la victime (entendue comme témoin en 2005 parce qu'elle était, alors, encore mineure). Ensuite, différents témoins qui, pour la plupart, avaient déjà été entendus en 2005, ont fait l'objet d'une nouvelle audition. Il en va ainsi de la dénommée C._, qui a été réentendue, à la requête expresse du recourant, sous son nouveau nom de E._ (Lettre du conseil du recourant au Tribunal correctionnel, du 3 novembre 2008). Quant au témoin D._, il a été entendu le 12 avril 2005 sur la question d'une inscription figurant sur un bâtiment scolaire. Il s'est alors engagé à se renseigner et à fournir des indications par écrit au tribunal. Les parties ont été informées du contenu de cette communication manuscrite, transmise le jour même. La pièce a été versée au dossier de la cause (procès-verbal du jugement de première instance, p. 3, 5 et 12; pièce 81 du dossier cantonal). Une nouvelle audition de cette personne ne s'imposait donc pas le 4 avril 2009, quelle que soit la composition de la cour. Il ne ressort, par ailleurs, pas du jugement de première instance que des faits auraient été établis sur la seule base de déclarations orales recueillies lors des deux audiences initiales. On ne perçoit, en conséquence, pas en quoi le recourant, aurait été privé d'un procès équitable.
Pour le surplus, le recourant n'invoque pas l'arbitraire dans l'application des art. 324, 365 et 366 CPP/VD (cf. <ref-ruling> consid. 3, p. 594 s.). Il se borne à énumérer les art. 29 à 32 Cst., ainsi que 6 et 13 CEDH. Il n'y a donc pas lieu d'examiner plus avant la cause sous l'angle constitutionnel et conventionnel, faute de griefs motivés à satisfaction de droit (art. 106 al. 2 LTF).
2. Le recourant conteste sa condamnation en application de l'art. 187 CP. Il ne nie pas avoir eu des relations sexuelles avec une jeune fille de moins de seize ans. L'arrêt cantonal constate, cependant, que si le recourant se doutait qu'elle était mineure (v. infra consid. 3.5, dernier paragraphe), il ignorait qu'elle n'avait pas atteint l'âge précité (arrêt entrepris, consid. 2b, p. 4). Ce que l'auteur sait ou ignore relève du fait (<ref-ruling>, consid. 3.1, p. 116), dont la constatation lie la cour de céans (art. 105 al. 1 LTF). Le litige porte ainsi exclusivement sur le caractère évitable de l'erreur du recourant (cf. art. 187 ch. 4 CP).
2.1 Cette dernière disposition réprime une forme de négligence (<ref-ruling> consid. 3, p. 142). Il convient donc de déterminer l'étendue des précautions commandées par les circonstances ainsi que par la situation du recourant (art. 12 al. 3 CP; ancien art. 18 al. 3 CP) et si l'on peut reprocher à ce dernier, compte tenu de ses circonstances personnelles, d'avoir fait preuve d'un manque d'effort blâmable (<ref-ruling> consid. 3b p. 147 s. et les références citées).
2.2 Le jugement de première instance, auquel l'arrêt cantonal renvoie quant aux faits (arrêt entrepris, consid. B, p. 2), met en évidence bon nombre d'indices qui, juxtaposés, auraient nécessairement dû induire de la méfiance sur la prétendue majorité sexuelle de l'adolescente et conduire le recourant à prendre des précautions supplémentaires. Ce dernier, qui s'attendait à rencontrer lors du premier rendez-vous une personne de 27 ans, a été surpris de voir arriver la jeune fille. La demande, faite par celle-ci, à une occasion, qu'il se substitue à son père pour récupérer un téléphone portable dans un établissement d'enseignement devait susciter des soupçons supplémentaires, de même que les circonstances dans lesquelles elle avait fui son domicile en invoquant des problèmes avec sa mère et ses petites soeurs. Enfin, en octobre 2002, la victime avait indiqué une date de naissance ne correspondant pas non plus à l'âge imaginé par le recourant, ce qui avait amené ce dernier, comme il l'avait reconnu, à concevoir des doutes sur son âge effectif (jugement, consid. 2.2.3, p. 24 ss).
La jurisprudence se montre exigeante dans la définition du devoir de prudence, en cas d'hésitation sur la majorité sexuelle d'un partenaire. Sous réserve des éventuelles circonstances concrètes susceptibles de conduire l'auteur à croire sérieusement que la personne avec qui il entretient une relation de cette nature a plus de seize ans (<ref-ruling>), celui qui a conscience que la victime est proche de la limite de l'âge de protection doit faire preuve d'une attention accrue. Il ne peut se contenter d'évacuer ses doutes sur la base de la réponse donnée à une simple question, en particulier lorsqu'il a la possibilité de se renseigner auprès de tiers (<ref-ruling>). Le Tribunal fédéral a aussi souligné que, d'expérience, de jeunes filles peuvent mentir sur leur âge pour être prises au sérieux par des hommes plus mûrs qu'elles et entretenir de cette manière l'intérêt qu'elles ont suscité (<ref-ruling>). Ces principes résultent du simple bon sens et de l'expérience générale. La pratique plus récente les applique encore, notamment lorsque la différence d'âge est importante et qu'il apparaît qu'un partenaire sexuel pourrait être proche de la limite légale (arrêt non publié du 13 novembre 2007, 6B_214/2007, consid. 3.3). Le Tribunal fédéral ne les a tempérés que dans le cas des amours juvéniles. Il s'agit, dans ce contexte, de tenir compte de la volonté du législateur de décriminaliser les situations dans lesquelles l'auteur et la victime ont pratiquement le même âge, lorsque des circonstances particulières le justifient ou qu'une relation amoureuse s'est développée (cf. art. 187 ch. 3 et 4 CP; <ref-ruling> consid. 3, p. 142 ss).
2.3 Ces dernières conditions ne sont pas réalisées en l'espèce. On ne saurait donc reprocher aux autorités cantonales d'avoir formulé un certain niveau d'exigence quant au devoir de prudence qui incombait au recourant.
Le jugement constate que la succession des mensonges échafaudés par la jeune fille n'a plus échappé au recourant au-delà du 19 octobre 2002. Ces contre-vérités et le fait que celui-ci se soit, à la demande de celle-là, fait passer pour son père dans un établissement d'enseignement, démontrent suffisamment que le recourant devait nécessairement éprouver des doutes non seulement sur l'âge de la victime, mais aussi sur sa majorité sexuelle. Le recourant allègue en vain (art. 105 al. 1 LTF) avoir pu être trompé sur la nature réelle de l'institution en cause. Les premiers juges ont, en effet, écarté sa version des faits selon laquelle il croyait avoir à faire à une jeune femme, soit à une étudiante en droit à l'Université. Ils ont objecté, de manière convaincante, qu'il était invraisemblable que le recourant ait pu penser se faire remettre un téléphone mobile confisqué par le recteur de l'Université de Lausanne (jugement, consid. 2.2.3.b, p. 25). L'ensemble de ces circonstances imposait au recourant de procéder à des vérifications supplémentaires, même si la victime, qui savait faire preuve de maturité dans son discours, n'était pas sans ressources pour dissimuler son âge réel (jugement de première instance, consid. 2.2.1, p. 21). Les autorités cantonales ont relevé à juste titre, à ce propos, que le recourant accusait une importante différence d'âge avec elle, soit trente ans, et qu'il était lui-même père de plusieurs enfants. Son expérience de la vie devait l'amener à contrôler la date de naissance de sa partenaire. Il devait compter avec l'éventualité qu'elle exagère son âge pour pouvoir continuer sa relation avec lui (jugement de première instance, consid. 2.2.3.d, p. 26). On peut ajouter que le recourant, qui est venu chercher l'adolescente à son domicile, connaissait son adresse et aurait pu sans difficulté entrer en contact avec la mère de l'intéressée. En outre, la durée de la relation ainsi que le fait qu'elle s'est déroulée d'abord dans des hôtels en Suisse, puis à l'étranger, auraient fourni au recourant diverses occasions d'examiner plus attentivement les documents d'identité de la jeune fille. Cela permet d'imputer la négligence à un manque d'effort blâmable. Le grief est infondé.
3. Le recourant conteste, enfin, la qualification d'enlèvement de mineur.
3.1 L'art. 220 CP sanctionne, sur plainte, celui qui aura soustrait ou refusé de remettre un mineur à la personne qui exerce l'autorité parentale ou la tutelle. Cette disposition protège en premier lieu l'exercice des droits et obligations du détenteur de l'autorité parentale, soit en particulier sa prérogative primaire de décider du lieu de résidence de l'enfant mineur (art. 301 al. 1 et 3 CC). Elle tend aussi, de manière indirecte, à garantir la paix familiale et le bien de l'enfant (<ref-ruling> consid. 3.1, p. 159).
Pour que le délit soit consommé, il faut que l'auteur empêche le détenteur de la puissance paternelle ou le tuteur de décider, ainsi que la loi l'y autorise, du sort du mineur, de son lieu de résidence, de son éducation et de ses conditions de vie, notamment. Il faut entendre par soustraction ou refus de remettre, que la personne mineure a été éloignée ou tenue éloignée du lieu de séjour ou de placement que le détenteur de la puissance paternelle ou le tuteur avait choisi, ou encore que le détenteur de la puissance paternelle ou le tuteur n'a plus libre accès à son enfant ou à son pupille et ne peut plus communiquer librement avec lui. L'acte consiste en une séparation dans l'espace, sans qu'il y ait besoin de distinguer si c'est le mineur (avec ou sans son consentement) qui est tenu éloigné du détenteur de la puissance paternelle ou du tuteur ou si c'est l'inverse. Il suffit donc que l'exercice de la puissance paternelle ou de la tutelle soit directement entravé par l'éloignement du mineur de son lieu de séjour ou de placement ou par un obstacle qui ne le rend plus librement accessible, pour que l'acte tombe sous le coup de l'art. 220 CP (<ref-ruling> consid. 2, p. 304 s.).
3.2 La circonstance de l'éloignement géographique est clairement donnée en l'espèce. La minorité de l'adolescente est un fait constant. Les parents ignoraient où se trouvait leur enfant et n'étaient, partant, pas en mesure d'exercer leur autorité sur elle. Le recourant ne le conteste pas. Il soutient qu'il n'aurait que véhiculé l'intéressée après qu'elle s'est enfuie de son domicile. Il ne lui aurait apporté qu'une aide purement accessoire alors qu'elle avait déjà décidé de quitter la résidence familiale, indépendamment de son intervention.
3.3 Il est vrai que, selon la doctrine, le tiers qui apporte une aide purement accessoire au mineur qui s'enfuit ou refuse de retourner au lieu désigné par celui qui exerce l'autorité parentale ou la tutelle ne participe pas à une infraction (Bernard Corboz, Les infractions en droit suisse, vol. I, 2002, art. 220 CP, n. 28 et les références à Rehberg, Schubarth et Trechsel). Encore faut-il que ce tiers ne soit pas lui-même l'auteur du délit (Corboz, ibidem, et les références à Schubarth et Stratenwerth).
Les premiers juges n'ont pas retenu à la charge du recourant les faits survenus le 28 septembre 2002, au motif que son erreur sur l'âge de la victime excluait, au plan subjectif, l'infraction à l'art. 220 CP à ce moment-là. Il n'y a donc pas lieu d'examiner si, d'un point de vue objectif, le fait que le recourant a emmené l'adolescente dans sa voiture le 28 septembre 2002 constitue une simple aide accessoire ou suffit à réaliser l'infraction sous sa forme de la soustraction.
En revanche, dès le 19 octobre 2002, le recourant se doutait, selon le premier juge, que la jeune fille était mineure. Il avait, dès lors, pris le risque de la soustraire à l'autorité parentale. Il aurait dû prendre des mesures concrètes pour la ramener, ce qu'il n'avait pas fait (jugement de première instance, consid. 2.3, p. 27).
3.4 Cette motivation, à laquelle la cour cantonale s'est ralliée (arrêt entrepris, consid. II.5, p. 10) ne distingue pas clairement les deux comportements réprimés par l'art. 220 CP. En effet, en excluant de la qualification les actes du recourant antérieurs au 19 octobre 2002, les autorités cantonales ont considéré une période durant laquelle l'adolescente avait déjà rompu ses liens avec le ou les détenteurs de l'autorité parentale. Le recourant ne pouvait donc plus, durant cette période, soustraire la jeune fille au sens de la norme pénale. Seul entrait en ligne de compte un éventuel refus de remettre la mineure (cf. <ref-ruling> consid. 2b, p. 16).
3.5 Selon la jurisprudence, un tel refus peut être exprimé même par actes concluants, au travers d'une simple omission, ou encore en empêchant que l'enfant soit retrouvé (<ref-ruling> consid. 2c/bb, p. 17).
Dans le cas présent, il est établi que le recourant se doutait de la minorité de sa jeune compagne, dès le 19 octobre 2002 (jugement, consid. 2.3, p. 27). Il a emmené l'adolescente en France, à la demande de cette dernière, qui avait émis des craintes d'être inquiétée par la police en Suisse. Il a recherché une habitation dans la région de F._ avant de s'installer avec elle à B._ dans un appartement qu'il a loué. A l'aune du principe dit de subsidiarité (<ref-ruling> consid. 2.2 p. 121 s. et les références citées), le comportement du recourant doit être appréhendé comme actif. Il s'est inscrit dans la durée et manifestait clairement, au moins dès le 19 octobre 2002, son intention d'empêcher les parents d'exercer leur autorité parentale sur l'adolescente. On ne saurait y voir une simple aide accessoire.
3.6 Selon certains auteurs, celui qui refuse de restituer l'enfant mineur ne se rend pas coupable de l'infraction réprimée par l'art. 220 CP lorsque le retour échoue exclusivement en raison du refus du mineur capable de discernement et que l'auteur s'en remet à sa décision (Andreas Eckert, BSK, Strafrecht, 2e éd. 2007, art. 220 n. 28; Andreas Donatsch/Wolfgang Wohlers, Strafrecht IV, 3e éd. 2004, § 5, p. 27 s.; Stefan Trechsel, Kommentar, art. 220, n. 4; v. déjà Martin Schubarth, Kommentar zum Schweizerischen Strafrecht, tome 4, 1997, art. 220 CP, n. 10). La norme pénale protège cependant au premier chef la paix familiale, respectivement l'exercice de l'autorité parentale ou tutélaire (supra consid. 3.1), et non le mineur lui-même, dont la liberté est, par ailleurs, protégée par l'art. 183 CP (Schubarth, op. cit., art. 220 CP, n. 41). Une portée prépondérante ne peut donc pas être accordée à la seule volonté du mineur, au risque de détourner la norme pénale de son but (v. en ce sens Marie Schaefer-Altiparmakian, Aspects juridiques de l'enlèvement d'enfants par un parent, 2001, p. 75; Günter Stratenwerth, Schweizerisches Strafrecht, BT II, 4e éd. 1995, § 27, n. 6, p. 30). Aussi l'interprétation proposée par la doctrine précitée ne pourrait-elle, au mieux, être admise que dans d'étroites limites, soit lorsque le refus est patent et clairement établi et que le surmonter est réellement impossible ou, tout au moins, ne peut être exigé de l'auteur, comme l'admettent, du reste Donatsch et Wohlers (loc. cit.). Lorsque l'auteur ne se borne pas à laisser au mineur le choix du retour, mais prend des mesures concrètes qui ont pour effet d'empêcher les détenteurs de l'autorité parentale de l'exercer, il n'est plus possible de dire que le retour est empêché exclusivement par la volonté du mineur.
En l'espèce, les autorités cantonales ne constatent pas que le non-retour de A._ résulterait exclusivement de sa volonté. La cour de céans est liée sur ce point (art. 105 al. 1 LTF). Il est vrai que la mineure paraît avoir quitté le domicile familial de son propre chef à fin septembre. Cela ne permet cependant pas encore de conclure qu'elle aurait, dès le 19 octobre 2002, opposé un refus insurmontable pour le recourant. Au contraire, le fait que la jeune fille a continué, durant sa fugue, à envoyer des SMS à ses parents, sa mère en particulier, pour les rassurer (procès-verbal d'audition de A._, du 3 novembre 2002, p. 5) tend plutôt à démontrer que les rapports entre l'adolescente et les détenteurs de l'autorité parentale n'étaient pas irrémédiablement détériorés, même si l'intéressée expliquait aussi avoir espéré, de la sorte, que ses parents allaient cesser de la chercher. Par ailleurs, la relation sentimentale nouée avec elle par le recourant et le fait qu'il a non seulement accepté de l'héberger, mais l'a emmenée à l'étranger et y a loué une habitation exclut que l'on puisse imputer à la seule jeune fille le refus de réintégrer le domicile familial.
3.7 Le comportement actif du recourant, qui a emmené l'adolescente en France et y a recherché une habitation avant de s'installer avec elle dans un appartement qu'il a loué, manifestait son intention d'empêcher les détenteurs de l'autorité parentale d'exercer leurs prérogatives. Cet objectif a été atteint dès lors que l'adolescente n'a pu être retrouvée qu'au mois de novembre grâce à la police. Dans ces conditions, la condamnation du recourant en application de l'art. 220 CP ne viole pas le droit fédéral.
4. Le recourant supporte les frais de la procédure (art. 66 al. 1 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté dans la mesure où il est recevable.
2. Les frais judiciaires, arrêtés à 4000 fr., sont mis à la charge du recourant.
3. Le présent arrêt est communiqué à la représentante du recourant, au Ministère public du canton de Vaud, à G._ et H._ ainsi qu'au Tribunal cantonal du canton de Vaud, Cour de cassation pénale. A._ est informée qu'elle peut en obtenir gratuitement communication.
Lausanne, le 20 mai 2010
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Le Greffier:
Favre Vallat