Faits:
A. A._, ressortissant français, a été extradé de Belgique en Suisse au mois de juin 2007, pour l'exécution d'un jugement rendu par défaut en décembre 2003 (condamnation par le Tribunal d'arrondissement de l'Est vaudois à 8 mois de privation de liberté pour crime manqué d'escroquerie et faux dans les titres) et pour les besoins de trois instructions pénales en cours dans l'arrondissement de l'Est vaudois et le canton du Jura. L'extradition a été refusée pour l'exécution de deux jugements rendus en 1994 (condamnation par la Cour suprême du canton de Berne à 16 mois de détention avec sursis pour escroquerie) et 1999 (condamnation par le Tribunal correctionnel du Pays d'Enhaut à 2 ans de détention), car ces deux peines étaient prescrites en droit belge.
A._ a obtenu le relief du défaut prononcé en 2003; la peine a été ramenée à deux mois de privation de liberté. Par jugement du 19 novembre 2008, le Tribunal correctionnel de l'arrondissement de Lausanne l'a condamné à une peine privative de liberté de 34 mois de détention, sous déduction de 808 jours de détention préventive. Le 27 janvier 2009, le Juge d'application des peines du canton de Vaud (ci-après: le JAP) lui a accordé la libération conditionnelle, pour ces deux condamnations. Le 1er mars 2009, la Fondation vaudoise de probation, chargée du suivi probatoire de A._, a informé ce dernier par téléphone que le suivi était suspendu car il n'était pas autorisé à séjourner en Suisse. Le 8 avril 2009, l'Office vaudois d'exécution des peines l'a informé qu'il devait quitter sans délai la Suisse en raison d'une interdiction d'entrée prononcée le 12 janvier 2000 par l'Office fédéral des étrangers, et valable jusqu'au 11 janvier 2010. S'il demeurait en Suisse, il s'exposait à de nouvelles sanctions pénales et à une révocation de sa libération conditionnelle.
B. Le 25 avril 2009, A._ a été arrêté à l'Aéroport de Zurich, au retour d'un voyage en Russie et aux Etats-Unis, sur la base d'un signalement RIPOL réactivé par les autorités bernoises en vue de l'exécution de la condamnation prononcée en 1994. Berne ayant délégué l'exécution de cette condamnation aux autorités vaudoises, ces dernières ont repris à leur charge l'exécution des condamnations de 1994 et 1999.
A._ a formé une demande de libération conditionnelle.
Par arrêt du 25 juin 2009, le JAP a traité cette demande comme un recours contre l'arrestation et la mise à exécution des deux condamnations de 1994 et 1999, et l'a rejeté. La réserve de la spécialité, posée par la Belgique lors de l'extradition, était tombée en vertu des art. 14 par. 1 CEExtr. et 38 al. 2 let. b EIMP, l'intéressé étant resté en Suisse à l'issue du délai de répit. Il n'avait certes pas été informé des conséquences de l'expiration de ce délai. Toutefois, en vertu de la primauté du droit international, la CEExtr. devait prévaloir sur le droit national lorsque ce dernier n'avait pas pour but de favoriser la coopération internationale. Or, l'art. 14 CEExtr. n'exigeait pas que l'intéressé ait été informé des conséquences de la poursuite de son séjour en Suisse. Les autres conditions posées par cette disposition (élargissement définitif et possibilité de quitter le territoire suisse) étaient remplies.
C. A._ forme un recours auprès de la Cour pénale du Tribunal fédéral. Il demande la réforme de l'arrêt du JAP en ce sens que la décision de l'Office d'exécution des peines ordonnant la mise à exécution des peines prononcées en 1994 et 1999 est annulée, et que l'ordre est donné de le mettre immédiatement en liberté conditionnelle. Subsidiairement, il demande le renvoi de la cause au JAP pour nouvelle instruction et décision au sens des considérants. Il demande en outre l'assistance judiciaire.
La cause a été transmise à la Ire Cour de droit public, ce dont les parties ont été informées.
Après avoir confirmé qu'il n'existe aucune voie de droit cantonal contre l'arrêt attaqué, le JAP a renoncé à répondre au recours et s'est référé à son arrêt. L'Office fédéral de la justice, Unité Extraditions (ci-après: OFJ), conclut au rejet du recours.
Le recourant a répliqué et maintenu ses conclusions.
Considérant en droit:
1. Le litige a trait à l'exécution de deux peines prononcées en 1994 et 1999. La voie du recours en matière pénale est ouverte (art. 78 al. 2 let. b LTF). Le recourant, qui a participé à la procédure devant l'autorité précédente (art. 81 al. 1 let. a LTF), a un intérêt légitime au recours (art. 81 al. 1 let. b LTF).
1.1 Le recours est formé en temps utile (art. 100 al. 1 LTF), contre un arrêt rendu en dernière instance cantonale; selon l'indication des voies de droit figurant dans l'arrêt attaqué, ce dernier ne peut pas faire l'objet d'un recours cantonal; cela est confirmé à l'art. 37 al. 3 de la loi vaudoise sur l'exécution des condamnations pénales (LEP; RS/VD 340.01). La question de savoir si cette lacune est conforme aux exigences de l'art. 80 al. 2 LTF peut demeurer indécise, compte tenu du délai transitoire de l'art. 130 al. 1 LTF.
1.2 Le recours, adressé à la Cour pénale du Tribunal fédéral, a été transmis à la Ire Cour de droit public. En effet, si la première est compétente en matière d'exécution des peines (art. 33 let. a du règlement du Tribunal fédéral - RTF; RS 173.110.131), la seconde traite des recours en matière de droit public dans les domaines touchant à l'entraide judiciaire internationale en matière pénale, y compris l'extradition (art. 29 al. 1 let. d RTF), ainsi que les recours en matière de droit public portant sur la protection de la bonne foi (art. al. 2 let. b RTF) et les garanties judiciaires en matière de privation de liberté (art. 29 al. 2 let. g RTF). En l'occurrence, le recours porte essentiellement sur l'application du principe de la spécialité en matière d'extradition. Même s'il s'agit d'un recours en matière pénale, celui-ci peut être traité par la cour de céans en dérogation aux règles d'attribution, conformément à l'art. 36 al. 2 RTF.
2. Le recourant soutient que l'art. 38 al. 2 de la loi fédérale sur l'entraide internationale en matière pénale (EIMP; RS 351.1), qui exige que l'intéressé soit rendu attentif aux conséquences de l'écoulement du délai de répit, devrait prévaloir sur la disposition de l'art. 14 CEExtr. qui n'exige pas une telle information. En l'occurrence, le recourant n'a pas été informé des conséquences d'une prolongation de séjour ou d'un retour en Suisse. Il soutient par ailleurs que sa libération conditionnelle, assortie d'une probation, ne serait pas assimilable à un élargissement définitif au sens de la Convention européenne d'extradition (CEExtr.; RS 0.353.1).
2.1 La règle de la spécialité est un principe général du droit extraditionnel (ZIMMERMANN, La coopération judiciaire internationale en matière pénale, 3ème éd. Berne 2009 p. 689-690). Elle est notamment exprimée à l'art. 14 CEExtr., selon lequel l'individu extradé ne peut pas être détenu en vue de l'exécution d'une peine pour un fait antérieur à la remise et différent de celui qui a motivé l'extradition.
Le principe de la spécialité tend d'une part à la protection de la souveraineté de l'Etat requis, en permettant à ce dernier de définir précisément le cadre de sa collaboration et de fixer des conditions quant à la poursuite de la personne extradée, en tenant compte des spécificités de son propre droit. Il constitue d'autre part une garantie en faveur de la personne extradée (ATF 123 IV 42 consid. 3b p. 47; BERTRAND REEB, La raison d'État dans l'entraide internationale en matière pénale in: Du Monde pénal, Mélanges en l'honneur de Pierre-Henri Bolle, Bâle 2006, p. 235 ss, p. 236-237). Ce dernier aspect ressort clairement du fait que la personne extradée peut, aux conditions de l'art. 14 par. 1 let. b CEExtr., renoncer à cette protection, sans que la Partie qui l'a livrée n'ait à y consentir. Selon cette disposition en effet, l'extradé perd le bénéfice de la spécialité "lorsqu'ayant eu la possibilité de le faire, [il] n'a pas quitté dans les 45 jours qui suivent son élargissement définitif, le territoire de la Partie à laquelle il a été livré ou s'il y est retourné après l'avoir quitté". L'idée en est que la protection accordée à l'extradé contre des poursuites ou une exécution de peine pour des faits antérieurs à l'extradition ne doit pas durer indéfiniment (ATF 81 IV 285 consid. II/1b p. 291; arrêt 6S.299/1997 du 25 novembre 1998). On peut par ailleurs présumer que celui qui accepte, sans contrainte aucune, de demeurer à disposition des autorités de répression ou d'exécution de l'Etat où il se trouve, accepte aussi les conséquences de ce comportement et se soumet ainsi à la juridiction territoriale de cet Etat (ATF 118 Ib 462 consid. 2a p. 465-466).
En droit interne, l'art. 38 EIMP rappelle le principe de la spécialité, dans des termes analogues à ceux de l'art. 14 CEExtr. Il prévoit également un délai de répit de 45 jours au terme duquel le principe de la spécialité n'est plus opposable. Toutefois, l'art. 38 al. 2 let. b ch. 1 EIMP précise que la personne extradée doit préalablement "avoir été instruite des conséquences".
2.2 L'autorité intimée a considéré qu'en raison de la primauté du traité sur le droit interne, principe largement appliqué en matière d'entraide internationale, l'information préalable, non exigée à l'art. 14 CEExtr., n'était pas nécessaire pour faire courir le délai de répit. Dans la mesure où il ne favorisait pas la coopération internationale, l'art. 38 al. 2 EIMP n'était pas applicable.
2.3 La jurisprudence a rappelé à de nombreuses reprises qu'en présence d'un traité d'entraide judiciaire ou d'extradition destiné à favoriser la coopération internationale, il y a lieu en principe d'appliquer les dispositions qui permettent d'accorder l'entraide ou l'extradition aux conditions les plus favorables (ATF 125 II 569 consid. 10a p. 582; 123 II 134 consid. 1a p. 136; 122 II 485 consid. 3b p. 487, 140 consid. 2 p. 142; 120 Ib 189 consid. 2b p. 191-192). On peut y voir la consécration du principe dit "de faveur" (Günstigkeitsprinzip), tiré directement de la norme internationale lorsque le traité contient une telle réserve expresse ou dans la mesure où le traité tend à l'obtention d'une coopération "la plus large possible" (ATF 122 II 140 consid. 2 p. 142; ZIMMERMANN, op. cit. p. 224 ss). La jurisprudence rappelle en outre régulièrement que l'application de la norme la plus favorable doit avoir lieu dans le respect des droits fondamentaux (ATF 123 II 595 consid. 7c p. 617).
2.4 En l'occurrence, l'autorité intimée méconnaît que la collaboration internationale a pris fin avec l'acceptation par la Belgique, le 15 juin 2007, de la demande d'extradition, et par la remise du recourant à la Suisse le 7 août 2008. Après la libération conditionnelle du recourant, la décision de le remettre en détention pour l'exécution des condamnations prononcées en 1994 et 1999 ne constitue nullement un acte d'entraide. Au contraire, cette décision va à l'encontre de la volonté exprimée par l'Etat requis, puisque celui-ci a expressément refusé l'exécution des deux peines prescrites selon le droit belge. Dans un tel cas, l'autorité intimée ne pouvait se limiter à l'application du droit conventionnel en faisant abstraction des droits fondamentaux de la personne intéressée et en ignorant les conditions posées par le droit interne pour une mise à exécution des peines prononcées en Suisse.
2.5 L'OFJ soutient que l'art. 38 EIMP ne s'appliquerait qu'aux extraditions accordées par la Suisse. Cette opinion ne peut être suivie. L'EIMP régit l'ensemble des procédures relatives à la coopération internationale en matière pénale (cf. art. 1 al. 1 EIMP), y compris les demandes formées par les autorités suisses auprès d'un Etat étranger (cf. art. 30 al. 1 EIMP). En l'absence d'autres dispositions précisant la portée, pour les autorités suisses, du principe de la spécialité attaché à une extradition, l'art. 38 EIMP doit trouver à s'appliquer à tout le moins en tant que principe général.
2.6 Il en découle que le recourant devait, conformément à l'art. 38 al. 3 let. b ch. 1 EIMP, être instruit des conséquences encourues en cas de maintien de son séjour en Suisse (cf. ATF 118 Ib 462 consid. 2a p. 466, qui évoque ce devoir d'information, indépendamment de la teneur du droit conventionnel). Cette obligation découle également du principe de la bonne foi (art. 5 al. 3 Cst.), érigé en droit fondamental à l'art. 9 Cst.
2.7 Selon l'arrêt attaqué, il ressort clairement du dossier que les autorités d'exécution n'ont pas informé le recourant, lors de sa mise en liberté conditionnelle, de la teneur de l'art. 38 al. 2 EIMP et de ses conséquences. La décision d'extradition du Ministère belge de la Justice faisait clairement référence au principe de la spécialité, en rappelant que l'extradition n'était pas accordée pour les condamnations prononcées en 1994 et 1999. Cette décision ne fait en revanche aucune allusion au délai de répit. Le recourant a certes été informé, au mois de février 2009, du fait qu'il n'était pas autorisé à demeurer en Suisse en raison de l'interdiction d'entrée prononcée en l'an 2000. La probation a été suspendue pour cette raison. Le recourant a encore été rendu attentif, le 8 avril 2009, au fait qu'en demeurant en Suisse, il s'exposait à de nouvelles sanctions ainsi qu'à la révocation de sa libération conditionnelle. Ces communications n'équivalent toutefois pas à une information sur les conséquences juridiques liées à son séjour ou son retour en Suisse, du point de vue de son statut extraditionnel. Il en résulte que si le recourant est resté, respectivement est revenu sur le territoire suisse après sa mise en liberté, on ne peut présumer qu'il aurait ainsi accepté en toute connaissance de cause de se soumettre à la juridiction suisse. Contrairement à ce que soutient l'OFJ, la situation n'est pas différente suivant que l'intéressé demeure en Suisse ou y retourne à l'échéance du délai de répit.
3. Sur le vu de ce qui précède, le recours doit être admis. Dans un tel cas, le Tribunal fédéral peut statuer lui-même sur le fond ou renvoyer la cause à l'autorité précédente ou à celle qui a statué en première instance (art. 107 al. 2 LTF). En l'espèce, il apparaît que le principe de spécialité fait toujours échec à l'exécution des peines prononcées en 1994 et 1999, les conditions posées à l'art. 38 al. 2 let. a et b EIMP n'étant pas réunies. L'ordre d'exécution de ces peines doit par conséquent être annulé, et la cause renvoyée à l'autorité intimée afin qu'elle ordonne la mise en liberté immédiate du recourant, s'il n'existe pas d'autre titre de détention. Le Juge d'application des peines devra par ailleurs statuer à nouveau sur les frais et dépens de l'instance cantonale. Le recourant, qui obtient gain de cause, a droit à des dépens, à la charge du canton de Vaud. Cela rend sans objet sa demande d'assistance judiciaire. Conformément à l'art. 66 al. 4 LTF, il n'est pas perçu de frais judiciaires.
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis et l'ordre d'exécution des peines prononcées en 1994 et 1999 à l'encontre de A._ est annulé. La cause est renvoyée au Juge d'application des peines du canton de Vaud afin qu'il ordonne la mise en liberté du recourant, s'il n'existe pas d'autre titre de détention, et statue à nouveau sur les frais et dépens de l'instance cantonale.
2. Une indemnité de dépens de 2000 fr. est allouée au recourant, à la charge du canton de Vaud.
3. La demande d'assistance judiciaire est sans objet.
4. Il n'est pas perçu de frais judiciaires.
5. Le présent arrêt est communiqué à la mandataire du recourant, au Service pénitentiaire, Office d'exécution des peines, et au Juge d'application des peines du canton de Vaud, ainsi qu'à l'Office fédéral de la justice, Unité Extraditions.
Lausanne, le 17 septembre 2009
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Le Greffier:
Féraud Kurz