Sachverhalt:
A. Der 1954 geborene K._ verletzte sich am 2. Dezember 1998 bei einem Unfall an der rechten Schulter. Die Helsana Versicherungen AG (nachfolgend: Helsana), bei der er über seinen Arbeitgeber obligatorisch gegen Unfallfolgen versichert war, erbrachte die gesetzlichen Leistungen (Heilbehandlung; Taggeld). Am 1. April 2002 trat K._ eine andere Arbeitsstelle an. Über den neuen Arbeitgeber war er bei der Schweizerischen Unfallversicherungsanstalt (SUVA) obligatorisch unfallversichert. Ab 12. August 2002 war K._ wegen Schmerzen an der rechten Schulter wiederum vollständig arbeitsunfähig. Die Helsana, welcher dies am 2. September 2002 als Rückfall zum Unfall vom 2. Dezember 1998 gemeldet wurde, gewährte erneut Heilbehandlung und richtete Taggeld aus. Während des Bezugs dieser Leistungen erlitt K._ am 22. Oktober 2002 einen weiteren Unfall. Er zog sich dabei schwere Verletzungen zu, welche u.a. zu einer Paraplegie führten und eine gänzliche Arbeitsunfähigkeit bewirkten. Die SUVA, welcher dies am 5. November 2002 gemeldet wurde, verneinte ihre Leistungspflicht mit Schreiben an die Helsana vom 23. Dezember 2002. Zuständig sei gemäss <ref-law> in Verbindung mit <ref-law> die Helsana. Mit Schreiben an die SUVA vom 24. März 2003 bejahte die Helsana in Bezug auf die Schmerzen an der rechten Schulter einen Rückfall zum 2. Dezember 1998. Sie erklärte sich für den Rückfall und für den Unfall vom 22. Oktober 2002 als leistungspflichtig, da im Zeitpunkt des zweiten Unfalles noch eine volle Arbeitsunfähigkeit wegen des Rückfalls bestanden habe. Darauf kam die Helsana mit Schreiben vom 25. Juli 2006 zurück. Sie vertrat nunmehr die Auffassung, die SUVA habe aufgrund von <ref-law> die Leistungen für den Rückfall und für den Unfall vom 22. Oktober 2002 zu erbringen. Dementsprechend habe ihr die SUVA die für den Unfall vom 22. Oktober 2002 erbrachten Leistungen zurückzuvergüten. Nachdem sich die SUVA damit nicht einverstanden erklärt hatte, gelangte die Helsana an das Bundesamt für Gesundheit (BAG). Dieses stellte mit Verfügung vom 10. August 2007 fest, die SUVA sei in Analogie zu <ref-law> für den Rückfall (mit Arbeitsunfähigkeit seit 12. August 2002) und für den Unfall vom 22. Oktober 2002 gegenüber K._ leistungspflichtig, könne jedoch ihre Aufwendungen für den Rückfall von der Helsana zurückfordern.
B. Die SUVA erhob hiegegen Beschwerde. Das Bundesverwaltungsgericht hiess diese gut, hob die Verfügung des BAG vom 10. August 2007 auf und stellte fest, die Helsana sei für den Rückfall (mit Arbeitsunfähigkeit seit 12. August 2002) und den Unfall vom 22. Oktober 2002 leistungspflichtig und könne dafür keinen Rückgriff auf die SUVA nehmen (Entscheid vom 27. Januar 2009).
C. Die Helsana beantragt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, der Entscheid des Bundesverwaltungsgerichts sei aufzuheben und die streitige Leistungspflicht sei gemäss Verfügung des BAG vom 10. August 2007 zu regeln.
Die SUVA schliesst auf Abweisung der Beschwerde. K._ und das BAG verzichten auf eine Vernehmlassung.

Erwägungen:
1. Nach <ref-law> erlässt das BAG bei geldwerten Streitigkeiten zwischen Versicherern eine Verfügung. Das gilt auch bei negativen Kompetenzkonflikten zwischen zwei Versicherern betreffend die Leistungspflicht (<ref-ruling> E. 4c und d S. 181 f. mit Hinweisen). Die Verfügung des BAG ist mit Beschwerde beim Bundesverwaltungsgericht anfechtbar (Art. 31 in Verbindung mit Art. 32 und Art. 33 lit. d des Bundesgesetzes über das Bundesverwaltungsgericht [Verwaltungsgerichtsgesetz, VGG]). Gegen den Entscheid des Bundesverwaltungsgerichts kann beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten geführt werden (Art. 82 lit. a in Verbindung mit Art. 83 und Art. 86 Abs. 1 lit. a BGG). Beim hier angefochtenen Entscheid des Bundesverwaltungsgerichts handelt es sich um einen Endentscheid (<ref-law>). Die Helsana ist zur Beschwerde legitimiert (<ref-law>). Auf die, auch frist- und formgerecht eingereichte, Beschwerde ist daher einzutreten.
2. Gemäss <ref-law> werden die Versicherungsleistungen, soweit das Gesetz nichts anderes bestimmt, bei Berufsunfällen, Nichtberufsunfällen und Berufskrankheiten gewährt. Nach <ref-law> werden die Versicherungsleistungen - mit einem hier nicht interessierenden Vorbehalt - auch für Rückfälle und Spätfolgen gewährt.
Streitig und zu prüfen ist, welcher der beiden im Recht stehenden Unfallversicherer für den Rückfall zum Unfall vom 2. Dezember 1998 und für den Unfall vom 22. Oktober 2002 leistungspflichtig ist. In der Verfügung des BAG vom 10. August 2007 wurde die Beschwerdegegnerin für leistungspflichtig erklärt, im vorinstanzlichen Entscheid die Beschwerdeführerin.
3. Das Bundesverwaltungsgericht hat zunächst erkannt, dass die Beschwerdeführerin nicht befugt ist, gegenüber der Beschwerdegegnerin hoheitlich zu handeln, und demnach das Schreiben vom 24. März 2003 keine sie bindende Verfügung darstellen kann. Das ist richtig (<ref-ruling> E. 1b S. 327) und letztinstanzlich unbestritten.
4. Die Vorinstanz ist sodann zum Ergebnis gelangt, gemäss <ref-law> sei die Helsana leistungspflichtig. Diese macht geltend, es sei in analoger Anwendung von <ref-law> die SUVA als leistungspflichtig zu erklären.
4.1 Gemäss <ref-law> erbringt derjenige Versicherer die Leistungen, bei dem die Versicherung zur Zeit des Unfalls bestanden hat (Abs. 1 erster Satz; der zweite Satz betrifft die hier nicht interessierende Leistungspflicht bei Berufskrankheiten). Bei Nichtberufsunfällen erbringt derjenige Versicherer die Leistungen, bei dem der Verunfallte zuletzt auch gegen Berufsunfälle versichert war (Abs. 2). Der Bundesrat ordnet die Leistungspflicht und das Zusammenwirken der Versicherer u.a. bei einem erneuten Unfall (Abs. 3 Ingress und lit. b am Anfang). Dazu hat er <ref-law> erlassen, dessen vorliegend bedeutsame Absätze 1 und 2 wie folgt lauten:
1 Wenn der Versicherte erneut verunfallt, während er wegen eines versicherten Unfalles noch behandlungsbedürftig, arbeitsunfähig und versichert ist, so muss der bisher leistungspflichtige Versicherer auch die Leistungen für den neuen Unfall erbringen.
2 Verunfallt der Versicherte während der Heilungsdauer eines oder mehrerer Unfälle, aber nach der Wiederaufnahme einer versicherten Tätigkeit, erneut und löst der neue Unfall Anspruch auf Taggeld aus, so erbringt der für den neuen Unfall leistungspflichtige Versicherer auch die Leistungen für die früheren Unfälle. Die anderen beteiligten Versicherer vergüten ihm diese Leistungen, ohne Teuerungszulagen, nach Massgabe der Verursachung; damit ist ihre Leistungspflicht abgegolten. Die beteiligten Versicherer können untereinander von dieser Regelung abweichende Vereinbarungen treffen, namentlich wenn der neue Unfall wesentlich geringere Folgen hat als der frühere.
4.2 Die Vorinstanz ging davon aus, der vorliegende Sachverhalt könne aufgrund des Verordnungswortlauts sowohl unter <ref-law> ("... erneut verunfallt, während er wegen eines versicherten Unfalles noch behandlungsbedürftig, arbeitsunfähig und versichert ist, ...") wie auch unter <ref-law> ("... verunfallt ... während der Heilungsdauer eines oder mehrerer Unfälle, aber nach der Wiederaufnahme einer versicherten Tätigkeit ...") subsumiert werden. Entscheidend in der vorinstanzlichen Argumentation ist die Qualifikation des Rückfalls. Ein Rückfall sei nicht anders zu behandeln als der Unfall, auf den er zurückzuführen sei. Entsprechend sei <ref-law> mittels <ref-law> auch auf Rückfälle anwendbar. <ref-law> ziele daher zwar primär auf die Situation, in der ein Versicherter, nachdem er einen Unfall mit Arbeitsunfähigkeitsfolge erlitten habe, erneut verunfalle, bevor er eine neue Stelle bei einem andern Arbeitgeber angetreten habe. Darüber hinaus sei <ref-law> aber auch in jener Situation anwendbar, in der der Versicherungsschutz beim neuen Versicherer durch den Antritt der neuen Arbeitstätigkeit bereits einmal wirksam geworden sei, der frühere Arbeitgeber aber wegen des Rückfalls wieder "involviert wurde". Der Rückfall mit Arbeitsunfähigkeit sei dann das relevante Unfallereignis, welches das ursprüngliche Unfallereignis verdränge. Vorliegend sei der Versicherte aufgrund des Rückfalls vollständig arbeitsunfähig gewesen und habe im Zeitpunkt des zweiten Unfalls nicht wieder eine versicherte Tätigkeit aufgenommen. <ref-law> sei daher bereits aufgrund des Wortlauts nicht erfüllt. Die Helsana als für den Rückfall leistungspflichtiger Versicherer müsse gemäss <ref-law> auch für den zweiten Unfall einstehen.
4.3 Dieser Argumentation ist nicht zu folgen. Die <ref-law> und 97 ff. UVV regeln Sachverhalte, die sich aus der mehrfachen Trägerschaft der Unfallversicherung als Folge unterschiedlicher Arbeitsverhältnisse ergeben. Diese können zeitlich parallel (etwa bei mehreren Teilzeitarbeitsverhältnissen) oder zeitlich hintereinander liegen. Bei <ref-law> geht es einzig um die in solchen Fällen erforderliche zeitliche Abgrenzung der Arbeitsverhältnisse in Bezug auf die Zuständigkeit der Unfallversicherer. Das ergibt sich unmissverständlich aus der Grundnorm des Abs. 1 erster Satz dieser Bestimmung. Danach erbringt bei Berufsunfällen derjenige Versicherer die Leistungen, bei dem die Versicherung zur Zeit des Unfalles bestanden hat. An diese Regelung knüpft <ref-law> für die Nichtberufsunfälle an. <ref-law> enthält die Delegationsnorm für verschiedene Spezialfälle des zeitlichen Neben- oder Hintereinanders von Arbeitsverhältnissen. Im Hinblick darauf ist <ref-law> auszulegen.
4.4 <ref-law> normiert in diesem Sinn die Nachwirkungen des bisherigen Arbeitsverhältnisses vor der Aufnahme einer neuen versicherten Tätigkeit. Das ergibt sich zunächst unmissverständlich aus den Worten "während er wegen eines versicherten Unfalles noch behandlungsbedürftig, arbeitsunfähig und versichert ist, ... der bisher leistungspflichtige Versicherer ..." ("pendant qu'il est en traitement pour un accident couvert par l'assurance et qu'il est incapable de travailler, mais encore assuré, ... l'assureur tenu de lui verser les prestations jusqu'alors", "durante la cura per un infortunio coperto dall'assicurazione, è incapace di lavorare e ancora assicurato, ... l'assicuratore tenuto sino allora alle prestazioni" in der französischen resp. italienischen Textfassung der Bestimmung). Dem Wortlaut nach bezieht sich der Passus "wegen eines versicherten Unfalls" also nicht nur auf "noch behandlungsbedürftig und arbeitsunfähig", sondern auf alle drei Adjektive "noch behandlungsbedürftig, arbeitsunfähig und versichert". Besonders deutlich folgt dies aus der französischen und italienischen Fassung, wo das Wort "noch" ("encore", "ancora") unmittelbar vor dem Adjektiv "versichert" ("assuré", "assicurato") steht. Entscheidend für die Abgrenzung zu <ref-law> ist sodann dessen Formulierung "aber nach der Wiederaufnahme einer versicherten Tätigkeit", insbesondere die Worte "aber nach" ("mais après", "ma dopo").
Entsprechend regeln die Absätze 1 und 2 zwei zeitlich unterschiedliche Anwendungsbereiche und steht daher entgegen dem in <ref-ruling> E. 5c S. 73 Dargelegten der Abs. 2 nicht im Verhältnis einer lex specialis zum Abs. 1. Jener Entscheid betraf im Übrigen nicht wie der vorliegende die zeitliche Abgrenzung zwischen einer vorangehenden und einer nachfolgenden vollversicherten Tätigkeit. Vielmehr hatte der dortige Beschwerdeführer vor Eintritt des streitgegenständlichen Nichtberufsunfalls lediglich eine Teilzeitarbeit in geringem Umfang aufgenommen, welche jedenfalls hinsichtlich der Nichtberufsunfälle keinen Versicherungsschutz begründen konnte (<ref-ruling> E. 3b S. 69 f.). Damit gehörte er zur Kategorie der Teilversicherten (Alfred Maurer, Schweizerisches Unfallversicherungsrecht, 2. Aufl., S. 117; Maurer/Scartazzini/Hürzeler, Bundessozialversicherungsrecht, 3. Aufl., § 10 N 30). Bezüglich des eingetretenen Risikos Nichtberufsunfall beinhaltete die neu aufgenommene Teilzeitbeschäftigung somit keine "Wiederaufnahme einer versicherten Tätigkeit" im Sinn des <ref-law>, welche es von einer früheren versicherten Tätigkeit abzugrenzen galt.
4.5 Im Rahmen der dargelegten zeitlichen Abgrenzung regeln Art. 100 Abs. 1 und 2 UVV die Leistungspflicht bei einem "erneuten Unfall". Vorausgesetzt ist somit ein Unfallereignis. Der Rückfall ist kein erneuter Unfall. Er schliesst zwar Leistungspflichten an ein früheres Unfallereignis an, ist aber nicht selber ein solches (<ref-ruling> E. 2c S. 296). Soweit <ref-law> von einem erneuten Unfall spricht, kann daher nicht ein Rückfall gemeint sein (vgl. auch SVR 2003 UV Nr. 14 S. 42 E. 3 [U 86/02]). Nicht zu folgen ist daher insbesondere der Argumentation der Vorinstanz, bei der vorliegenden Konstellation gelte der Rückfall mit Arbeitsunfähigkeit als zeitlich erstes (hier relevantes) Unfallereignis; darüber hinaus bleibe das ursprüngliche Unfallereignis vom 2. Dezember 1998 ohne Bedeutung. Weil das Bundesverwaltungsgericht den Rückfall als erstes Unfallereignis qualifiziert, kommt es dann auch zum (falschen) Schluss, nach dem Rückfall und bis zum zweiten Unfall vom 22. Oktober 2002 habe der Versicherte nicht im Sinn von <ref-law> eine versicherte Tätigkeit wieder aufgenommen, sodass die Anwendung dieser Bestimmung ausscheide.
4.6 Mit der Delegationsnorm von <ref-law> wollte der Gesetzgeber, die "Leistungspflicht und das Zusammenwirken der Versicherungsträger bei ... Tatbeständen, die zu einer Kumulation oder zum Verlust von Leistungsansprüchen führen könnten" regeln (Botschaft vom 18. August 1976 zum UVG, BBl 1976 III 213). Auch die hier gegebene Konstellation würde zu einer solchen Kumulation führen, denn theoretisch hätte sowohl der erste Unfall (Rückfall) als auch der zweite Unfall je für sich zu einer vollen Arbeitsunfähigkeit geführt und damit Taggeldansprüche ausgelöst. Es ist daher anzunehmen, dass der Verordnungsgeber auch für die vorliegende Konstellation eine Koordinationsregel getroffen hätte, hätte er sie bedacht. Mit dem BAG ist davon auszugehen, dass einzig eine analoge Anwendung von <ref-law> zu einer Lösung führt, welche den Absichten des Gesetzgebers entspricht. Die SUVA ist demnach für die Folgen des zweiten wie auch des ersten Unfalls (Rückfall) leistungspflichtig. Dies, obwohl der zweite Unfall im konkreten Fall keinen Anspruch auf Taggeld auslöste, da der Versicherte bereits aufgrund des Rückfalls arbeitsunfähig war und Taggeld bezog. <ref-law> ist daher nur analog anwendbar, weil - hätte der Taggeldanspruch nicht bereits wegen des Rückfalls bestanden - der zweite Unfall auf jeden Fall im Sinn der Norm einen Anspruch auf Taggeld ausgelöst hätte. Die SUVA hat aber gegenüber der Helsana einen Anspruch auf Rückvergütung nach Massgabe der durch den ersten Unfall beziehungsweise Rückfall verursachten Leistungen (Art. 100 Abs. 2 zweiter Satz UVV). Damit ist der Grundregel des Art. 77 Abs. 1 erster Satz UVG entsprochen, soweit es die Koordination zulässt. Würde demgegenüber entsprechend der Vorinstanz <ref-law> analog angewendet, müsste die Helsana auch die Leistungen für den Zweitunfall vollumfänglich tragen, ohne Rückvergütungsanspruch gegenüber der SUVA. Das steht in klarem Gegensatz zur Grundregel des <ref-law>.
5. Erstinstanzlich hatte die SUVA noch geltend gemacht, falls von der grundsätzlichen Anwendbarkeit von <ref-law> ausgegangen werde, hätten die Parteien gestützt auf das Schreiben der Helsana vom 24. März 2003 eine von <ref-law> abweichende Vereinbarung über die Leistungspflicht getroffen. Die Beschwerdeführerin bestritt das Vorliegen eines Vertrages. Nachdem die Vorinstanz gestützt auf <ref-law> eine Leistungspflicht der Helsana bejaht hatte, ging sie auf diese Eventualbegründung nicht ein. Die SUVA hält in ihrer letztinstanzlichen Vernehmlassung daran fest.
5.1 Art. 100 Abs. 2 letzter Satz UVV lässt abweichende Vereinbarungen zwischen den Versicherern zu. Das Zustandekommen eines solchen Vertrages ist, wenn keine öffentlich-rechtliche Regelung besteht, nach den im Privatrecht geltenden Grundsätzen zu prüfen (vgl. SVR 2008 UV Nr. 18 S. 65 E. 2 mit Hinweisen [8C_324/2007]; IMBODEN/RHINOW, Schweizerische Verwaltungsrechtsprechung, 6. Aufl. 1986, Bd. I, Nr. 46 B; RHINOW/KRÄHENMANN, Schweizerische Verwaltungsrechtsprechung, Ergänzungsband, 1986, Nr. 2 B V d und Nr. 46 X).
5.2 Die Ausführungen der SUVA zum Zustandekommen eines solchen Vertrages sind sehr knapp. Sie macht lediglich geltend, das Schreiben der Helsana vom 24. März 2003 müsse als Vertrag "interpretiert" werden. Es helfe der Helsana nicht, wenn sie behaupte, sie sei bei Verfassen dieses Schreibens nur versehentlich davon ausgegangen, nach der Regelung von <ref-law> leistungspflichtig zu sein. Vielmehr habe sie, die SUVA, nach Treu und Glauben im Geschäftsverkehr sich darauf verlassen dürfen, dass die Helsana die Sach- und Rechtslage damals einlässlich geprüft habe und auf ihre vorbehaltlos anerkannte Leistungspflicht nicht mehr zurückkomme.
Damit behauptet die SUVA nicht eine tatsächliche Willensübereinstimmung (natürlicher Konsens), sondern lediglich einen normativen Konsens (vgl. <ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 3.1 S. 632; <ref-ruling> E. 2b S. 39 f., je mit Hinweisen; EUGEN BUCHER, Basler Kommentar, Obligationenrecht, 4. Aufl. 2007, N 6 ff. zu <ref-law>).
5.3 Ob ein normativer Konsens vorliegt, ist eine Rechtsfrage (ULRICH MEYER, Basler Kommentar, Bundesgerichtsgesetz, 2008, N 35a zu <ref-law>; <ref-ruling> E. 2.2.1 S. 67; <ref-ruling> E. 3.1 S. 632, je mit Hinweisen), die das Bundesgericht von Amtes wegen prüfen kann (<ref-law>; LAURENT MERZ, Basler Kommentar, Bundesgerichtsgesetz, 2008, N 54 zu <ref-law>).
Ein normativer Konsens setzt voraus, dass die SUVA nach Treu und Glauben von einem entsprechenden Bindungswillen der Helsana ausgehen durfte und musste (BGE <ref-ruling> E. 3.1 S. 632 mit Hinweisen). Das würde voraussetzen, dass die Frage, ob <ref-law> anwendbar sei, zwischen den Parteien in jenem Zeitpunkt umstritten gewesen oder jedenfalls diskutiert worden wäre. Dem Schreiben vom 24. März 2003 konnte jedoch nur entnommen werden, dass die Helsana die Frage, ob ein Rückfall vorlag, geprüft hatte und, dies bejahend, ohne weitere Abklärungen davon ausging, dann bestehe von Gesetzes wegen zwangsläufig eine entsprechende Leistungspflicht. Hingegen durfte aus diesem Schreiben nicht in guten Treuen abgeleitet werden, die Helsana habe im Sinne des letzten Satzes von <ref-law> eine von der Grundregelung dieser Bestimmung abweichende Vereinbarung treffen wollen. Als Indiz gegen einen solchen Verpflichtungswillen der Helsana mag im Übrigen betrachtet werden, dass solche Vereinbarungen gemäss dem Verordnungswortlaut namentlich dann geschlossen werden können, wenn der neue Unfall wesentlich geringere Folgen hat als der erste. Dies trifft hier gerade nicht zu; die Folgen des zweiten Unfalls sind schwerwiegender als die des ersten.
6. Für den Fall, dass auch eine vertragliche Abrede verneint wird, beruft sich die Beschwerdegegnerin schliesslich erneut auf eine Verletzung von Treu und Glauben; auch die Grundsätze über die Verbindlichkeit unrichtiger behördlicher Auskünfte müssten analog herangezogen werden.
Letzteres trifft offensichtlich nicht zu, nachdem die Beschwerdeführerin wie dargelegt gegenüber der Beschwerdegegnerin nicht hoheitlich handeln kann (E. 3 hievor). Zwischen gleichrangigen Rechtssubjekten kann sich hingegen die Frage stellen, ob aufgrund von Treu und Glauben beziehungsweise des Vertrauensprinzips eine vertragliche Bindung zustande gekommen ist. Dabei könnte nur eine Vereinbarung im Sinne von Art. 100 Abs. 2 letzter Satz UVV von Interesse sein. Eine solche Vereinbarung liegt nach dem Gesagten nicht vor (E. 5 hievor). Sodann liesse sich fragen, ob ein Schadenersatzanspruch entstanden ist. Einen solchen machte die Beschwerdegegnerin vorinstanzlich geltend. Dies ist jedoch nicht Gegenstand des vorliegenden Verfahrens.
7. Nach dem Gesagten ist die Beschwerde der Helsana begründet und der angefochtene Entscheid aufzuheben. Die demnach unterliegende SUVA hat die Kosten des Verfahrens zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen und der Entscheid des Bundesverwaltungsgerichts vom 27. Januar 2009 aufgehoben.
2. Die Gerichtskosten von Fr. 3000.- werden der Beschwerdegegnerin auferlegt.
3. Dieses Urteil wird den Parteien, dem Bundesverwaltungsgericht und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 5. August 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Lanz