Faits:
A. A.a Du 1er décembre 1995 au 30 novembre 1997, R._ a bénéficié d'un délai-cadre d'indemnisation de l'assurance-chômage. Son gain assuré a été fixé à 3'600 fr.
Par contrat de travail du 1er avril 1996, l'assurée a été engagée par F._, titulaire de la raison individuelle T._, à L._ dont les actifs et passifs ont par la suite été repris par la société T._ à L._ également. Elle travaillait en qualité de secrétaire et il était prévu qu'elle perçoive un salaire de 1000 fr. par mois, à raison d'un taux d'occupation de "30% (environ 12 heures par semaine)". En janvier 1998, elle a épousé F._.
Pour la période courant dès le mois d'avril 1996, la Caisse cantonale vaudoise de chômage (ci-après: la Caisse) a indemnisé R._ en prenant en considération un gain intermédiaire de 150 fr. à 1'000 fr. par mois conformément aux attestations établies par l'employeur.
A.b Le 30 septembre 1998, le Service de l'emploi du canton de Vaud a nié le droit aux indemnités de chômage de R._ avec effet rétroactif au 1er avril 1996. Il a constaté que le gain intermédiaire déclaré n'était pas conforme, pour le travail effectué, aux usages professionnels et locaux, R._ ayant réalisé un surplus de travail important "à titre bénévole". Le Tribunal administratif vaudois a rejeté le recours de l'assurée par jugement du 28 février 2005.
Cette dernière a déféré la cause au Tribunal fédéral des assurances. Par arrêt du 18 juillet 2006 (cause C 107/05), celui-ci a annulé le jugement du Tribunal administratif vaudois ainsi que la décision du Service de l'emploi et a renvoyé la cause à ce dernier afin qu'il "détermine le montant des gains intermédiaires réalisés (en partie fictivement) par la recourante correspondant au salaire déclaré à l'assurance-chômage, ainsi qu'à un gain conforme aux usages professionnels et locaux pour une activité supplémentaire à 45%".
A.c Parallèlement à cette procédure, la Caisse a réclamé à R._ la restitution de 41'231 fr. 20, par décision du 14 octobre 1998. D'après la Caisse, ce montant correspondait aux indemnités touchées à tort du 1er avril 1996 au 30 novembre 1997. R._ s'est opposée à la restitution par acte du 12 novembre 1998.
Après avoir pris connaissance de l'arrêt du Tribunal fédéral des assurances du 18 juillet 2006, la Caisse a réduit ses prétentions. Par décision du 16 avril 2007, elle a demandé à R._ la restitution de la somme de 33'949 fr., en précisant que cette décision annulait et remplaçait celle du 14 octobre 1998.
La Caisse a maintenu cette demande de restitution par décision sur opposition du 6 décembre 2007.
B. R._ a déféré la cause au Tribunal des assurances du canton de Vaud en invoquant notamment la péremption de la créance dont se prévalait la Caisse. Par jugement du 16 juin 2009, les juges cantonaux ont rejeté le recours et réformé la décision litigieuse au détriment de l'assurée; ils ont condamné cette dernière à restituer un montant 36'371 fr. 35 au lieu de 33'949 fr.
C. R._ a formé un recours en matière de droit public contre ce jugement. Elle en demande la réforme en ce sens que soit constatée l'absence de créance de la Caisse en restitution des prestations allouées entre 1996 et 1997.
L'intimée s'en est remise à justice et le Secrétariat d'État à l'économie (SECO) a renoncé à se déterminer.

Considérant en droit:
1. Interjeté par une partie directement touchée par la décision et qui a un intérêt digne de protection à son annulation (<ref-law>), le recours, dirigé contre un jugement final (<ref-law>) rendu dans une cause de droit public (<ref-law>) par une autorité cantonale de dernière instance (art. 86 al. 1 let. d LTF), est recevable, puisqu'il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi et que l'on ne se trouve pas dans l'un des cas d'exceptions mentionnées par l'<ref-law>.
2. R._ ne conteste pas que les prestations dont la Caisse exige la restitution lui ont été versées indûment. Elle s'oppose cependant à la restitution au motif que la créance serait périmée.
3. 3.1 Aux termes de l'<ref-law>, dans sa teneur en vigueur jusqu'au 31 décembre 2002, la Caisse est tenue d'exiger du bénéficiaire la restitution des prestations auxquelles il n'avait pas droit (al. 1). Le droit de répétition se prescrit par une année après que l'organe qui a payé a eu connaissance du fait, mais au plus tard cinq ans après le versement de la prestation. Lorsque le droit de répétition découle d'un délit pour lequel le droit pénal prévoit un délai de prescription plus long, celui-ci est déterminant (al. 4). Depuis le 1er janvier 2003, sous réserve de cas particuliers sans rapport avec la présente procédure, l'obligation de restituer est prévue par l'<ref-law>, auquel renvoie désormais l'<ref-law>. Comme auparavant, le droit de demander la restitution s'éteint un an après le moment où l'institution d'assurance a eu connaissance du fait, mais au plus tard cinq ans après le versement de la prestation. Si la créance naît d'un acte punissable pour lequel le droit pénal prévoit un délai de prescription plus long, celui-ci est déterminant (<ref-law>). Nonobstant la terminologie légale, il s'agit de délais de péremption (<ref-ruling> consid. 1 p. 382; <ref-ruling> consid. 5a p. 274). Ces délais ne peuvent par conséquent pas être interrompus. Lorsque l'autorité a accompli l'acte conservatoire que prescrit la loi, le délai se trouve sauvegardé, cela une fois pour toutes (arrêt C 271/04 du 21 mars 2006 consid. 2.5; voir également André Pierre Holzer, Verjährung und Verwirkung der Leistungsansprüche im Sozialversicherungsrecht, 2005, p. 40 s.; Andrea Braconi, Prescription et péremption dans l'assurance sociale, in Droit privé et assurances sociales, 1990, p. 230).
3.2 Selon la jurisprudence, le délai de péremption relatif d'une année commence à courir dès le moment où la caisse de chômage aurait dû connaître les faits fondant l'obligation de restituer, en faisant preuve de l'attention que l'on pouvait raisonnablement exiger d'elle (ATF <ref-ruling> consid. 5a p. 274). La caisse doit disposer de tous les éléments qui sont décisifs dans le cas concret et dont la connaissance fonde - quant à son principe et à son étendue - la créance en restitution à l'encontre d'une personne déterminée, tenue à restitution (<ref-ruling> consid. 3 p. 17). Le délai de péremption d'une année commence à courir dans tous les cas aussitôt qu'il s'avère que les prestations en question étaient indues (arrêt K 70/06 du 30 juillet 2007 consid. 5.1). Cette jurisprudence vise un double but, à savoir obliger l'administration à faire preuve de diligence, d'une part, et protéger l'assuré au cas où celle-ci manquerait à ce devoir de diligence, d'autre part.
Le délai de péremption absolu de cinq ans commence à courir à la date du versement effectif de la prestation (<ref-ruling> consid. 4a p. 182; <ref-ruling> consid. 3 in fine p. 17). Il met un point final à un rapport d'obligation entre l'assurance et le débiteur.
4. 4.1 Il ne ressort pas des faits constatés par les premiers juges que la Caisse aurait eu connaissance de circonstances pouvant fonder une obligation de restituer avant la décision du 30 septembre 1998 du Service de l'emploi. Le délai relatif de l'art. 95 al. 4 aLACI a donc commencé à courir dès cette date, de sorte que la décision de restitution du 14 octobre 1998 a été rendue en temps utile.
4. 4.1 Il ne ressort pas des faits constatés par les premiers juges que la Caisse aurait eu connaissance de circonstances pouvant fonder une obligation de restituer avant la décision du 30 septembre 1998 du Service de l'emploi. Le délai relatif de l'art. 95 al. 4 aLACI a donc commencé à courir dès cette date, de sorte que la décision de restitution du 14 octobre 1998 a été rendue en temps utile.
4.2 4.2.1 La recourante soutient qu'une fois cette décision rendue, le délai relatif de péremption a recommencé à courir et qu'il est arrivé à échéance avant la nouvelle décision de restitution rendue le 16 avril 2007. En restant inactive entre ces deux décisions, la Caisse a laissé la créance se périmer. Toujours d'après la recourante, en niant cette péremption les premiers juges ont violé un principe général d'après lequel tout débiteur peut paralyser un droit en cas d'inaction prolongée du créancier. A défaut, la situation du débiteur « serait insupportable » et finalement, contraire au « droit de la personnalité ».
4.2.2 Les prétentions découlant du droit public sont généralement soumises à prescription ou à péremption afin d'assurer - comme en droit privé - une stabilité juridique et d'empêcher la remise en cause de situations qui ont duré pendant une certaine période (voir ANDREA BRACONI, op cit., p. 215). Dans le contexte de l'obligation de restituer des prestations d'assurance-chômage, cette question est réglée par des délais de péremption, et non de prescription, prévus par l'article 95 al. 4 aLACI jusqu'au 31 décembre 2002 et par l'article 25 LPGA depuis le 1er janvier 2003. Or, comme on l'a vu, un tel délai de péremption est sauvegardé une fois pour toutes lorsque l'autorité a accompli l'acte conservatoire que prescrit la loi; il ne recommence donc pas à courir (cf. consid. 3 supra).
En l'occurrence, l'intimée a sauvegardé le délai par une décision de restitution à laquelle l'assurée a fait opposition. Si cette dernière estimait que l'autorité tardait trop à clarifier la situation en statuant sur opposition, elle n'était pas totalement démunie, contrairement à ce qu'elle soutient, mais disposait de la voie du recours pour déni de justice. Dans la mesure où la recourante soutient que le délai de péremption litigieux a recommencé à courir après la décision du 14 octobre 1998, le recours est mal fondé.
5. 5.1 La recourante prétend également que la Caisse ne peut plus se prévaloir de l'interruption de la péremption par la décision du 14 octobre 1998, dès lors que celle-ci a été annulée par celle du 16 avril 2007, avec effet rétroactif.
5.2 Dans un arrêt C 19/03 du 17 décembre 2003, le Tribunal fédéral a distingué les décisions de restitution sur opposition annulées dans une procédure judiciaire de recours et renvoyées pour nouvelle décision à l'autorité inférieure, des décisions annulées par une autorité administrative sans garantie d'une nouvelle décision dans un délai raisonnable. Dans la première hypothèse, le délai est sauvegardé par la décision de restitution annulée par le juge pour la somme prévue initialement (cf. arrêts C 17/03 du 2 septembre 2003 consid. 4.2 s., in SVR 2004 AlV n°5 p. 13 et C 31/00 du 19 septembre 2000 consid. 2b, in DTA 2001 n°10 p. 91). Dans la deuxième hypothèse, le délai de péremption n'est pas réputé sauvegardé par la décision de restitution qui a été annulée. L'arrêt C 19/03 portait précisément sur une telle situation: une décision de restitution rendue en temps utile est entrée en force, puis a été annulée par voie de reconsidération; ultérieurement l'administration a rendu une nouvelle décision de restitution, jugée tardive par le Tribunal fédéral des assurances.
5.3 Dans le présent litige, l'intimée a été saisie d'une opposition contre la décision du 14 octobre 1998. Plutôt que de rendre une décision sur opposition, elle a préféré annuler la décision initiale et la remplacer sur le champ par une seconde décision de restitution ouvrant la voie à une nouvelle procédure d'opposition. La recourante savait donc dès la décision initiale du 14 octobre 1998 que la Caisse exigeait la restitution des prestations indues. Par la suite, elle est restée constamment partie à une procédure d'opposition portant sur la créance litigieuse et n'a jamais eu de motifs raisonnables de penser que la Caisse allait abandonner ses prétentions. Dans ces conditions, on se trouve dans une situation analogue à celle tranchée dans les arrêts C 17/03 et C 31/00 cités. Par conséquent, il faut considérer que le délai de péremption a été valablement sauvegardé par la première décision de restitution rendue par la Caisse.
6. Compte tenu de l'issue du litige, les frais judiciaires sont mis à la charge de la recourante, qui supportera également ses propres dépens (art. 66 al. 1 ainsi que 68 al. 1 et 2 LTF)

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 500 fr., sont mis à la charge de la recourante.
3. Le présent arrêt est communiqué aux parties, à la Cour des assurances sociales du Tribunal cantonal vaudois et au Secrétariat d'Etat à l'économie.
Lucerne, le 14 décembre 2009
Au nom de la Ire Cour de droit social
du Tribunal fédéral suisse
Le Président: Le Greffier:
Ursprung Métral