Sachverhalt:
A. T._ (geb. 1950, gest. am 17. Oktober 2008) und B._ (geb. 1948) sind respektive waren bei der CSS Kranken-Versicherung AG obligatorisch krankenpflegeversichert. T._ reichte dem Krankenpflegeversicherer eine Rechnung des Zentrums S._ im Betrag von EUR 4165.- wegen eines notfallmässigen Spitalaufenthalts vom 17. bis zum 29. Juni 2004 ein. B._ legte seinerseits eine Rechnung im Betrag von EUR 1673.- für einen Spitalaufenthalt vom 15. bis 26. Juni 2004 vor. Der Versicherungsträger liess die Umstände der geltend gemachten Spitalaufenthalte über eine Organisationszentrale für Auslandfälle abklären. Die betreffenden Ergebnisse führten ihn zum Schluss, die eingereichten Belege seien gefälscht. Demzufolge lehnte der Krankenpflegeversicherer die Kostenübernahme ab (mit Einspracheentscheiden vom 3. September 2007 bestätigte Verfügungen vom 20. Januar 2006).
B. Das Sozialversicherungsgericht des Kantons Zürich wies die dagegen erhobenen Beschwerden ab (Entscheide vom 31. Januar 2009).
C. B._ führt, auch in der Eigenschaft als Rechtsnachfolger seiner verstorbenen Ehefrau, gegen beide Entscheide Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem sinngemässen Rechtsbegehren, der angefochtene Entscheid sei aufzuheben und die CSS Kranken-Versicherung AG zu verpflichten, die geltend gemachten Auslagen zu erstatten. Ausserdem ersucht er um unentgeltliche Prozessführung.
Die CSS Kranken-Versicherung AG schliesst auf Abweisung der Beschwerde. Das Bundesamt für Gesundheit verzichtet auf eine Stellungnahme.

Erwägungen:
1. Mit Blick auf die weitgehende Parallelität der beiden Verfahren rechtfertigt es sich, diese zu vereinigen und mit einem einzigen Urteil zu erledigen (vgl. <ref-ruling> E. 1 S. 126 mit Hinweisen).
2. Strittig ist, ob der Krankenpflegeversicherer den von den Versicherten eingereichten Belegen entsprechend für die Kosten von aus medizinischen Gründen im Ausland erbrachten (<ref-law>) Behandlungen der T._ und des B._ über insgesamt EUR 5838.- aufzukommen hat.
2.1 Das kantonale Gericht kam zum Schluss, es sei zwar nicht gänzlich auszuschliessen, dass die fraglichen Behandlungen stattgefunden hätten; ihre tatsächliche Durchführung erscheine angesichts der Aktenlage jedoch als unwahrscheinlich.
2.1.1 Betreffend die strittige Behandlung der T._ erwog die Vorinstanz, die vom Krankenpflegeversicherer mit Abklärungen betraute M._ AG habe zur angeblichen operativen Behandlung einer Hernia ventralis (Bauchwandbruch) mit Einlage eines Netzes (Mesh) und stationärer Hospitalisierung im Zeitraum vom 17. bis 29. Juni 2004 mitgeteilt, das auf den Dokumenten aufgeführte Zentrum S._ stimme nicht mit dem Spital K._ überein, dessen Stempel verwendet worden seien. Im Zentrum S._ seien die aufgeführten Ärzte nicht bekannt. T._ sei in der dortigen Patientenkartei nicht registriert. Das Zentrum S._ habe weder Rechnungen an T._ ausgestellt noch Zahlungen von ihr erhalten. Auch im Medizinischen Zentrum K._ sei sie nicht verzeichnet. Diese Angaben würden durch die nach Erlass der Verfügung vom 20. Januar 2006 unternommenen Erhebungen bestätigt (Schreiben des Medizinischen Zentrums K._ vom 23. August 2007 sowie des Zentrums S._ vom 25. Oktober 2007). Somit könne nicht von der Echtheit und inhaltlichen Richtigkeit der vorgelegten Spitalunterlagen ausgegangen werden. Die konsiliarische Beurteilung durch die Internistin Dr. C._ vom 19. Januar 2007 habe zudem ergeben, dass bis dahin drei Eingriffe im Bereich des Abdomens durchgeführt worden seien. Das vom behandelnden Arzt in der Schweiz bestätigte Vorhandensein von Narben besage daher nichts. Anlässlich einer am 23. Februar 2007 erfolgten Operation im Spital X._ wegen rezidivierender Tumoren habe ausgeschlossen werden können, dass zuvor ein Netz eingesetzt worden sei.
2.1.2 Hinsichtlich der eingereichten Belege über eine Behandlung des B._ vom 15. bis 26. Juni 2004 in A._ wegen Pankreatitis (Bauchspeicheldrüsenentzündung) wies das kantonale Gericht auf die im Wesentlichen gleichen Umstände hin. Zusätzlich führte die Vorinstanz aus, der Umstand allein, dass auf den Dokumenten eines Spitals in S._ der Stempel eines Spitals in K._ angebracht sei, lasse Zweifel an der Zuverlässigkeit der darin enthaltenen Angaben aufkommen. Zudem seien die in einem (undatierten) Bericht angegebenen Behandlungskosten von "Fr. 500 8 Tage" kaum mit dem Rechnungsbetrag in Höhe von EUR 1673.- vereinbar. Die Beschwerdegegnerin weise zu Recht darauf hin, dass sich die Unterschriften eines Dr. I._ auf diesem Bericht und der quittierten Rechnung erheblich unterschieden. Bei der Beweiswürdigung dürfe schliesslich nicht ausser Acht bleiben, dass die Ehefrau des Beschwerdeführers ebenfalls Behandlungskosten für eine im Juni 2004 erfolgte stationäre Behandlung in A._ geltend mache und dabei ihren Anspruch ebenfalls auf mit Stempeln des Medizinischen Zentrums K._ versehene Dokumente des Zentrums S._ stütze; der zuständige Direktor habe in Bezug auf jene Dokumente ausdrücklich festgehalten, die darin aufgeführten Ärzte existierten nicht.
2.2 Der Beschwerdeführer macht geltend, er habe die strittigen Rechnungen in bar beglichen. Dies werde durch die unterzeichneten Rechnungen bestätigt. Hausarzt und Spital X._ bestätigten wiederum, dass seine Ehefrau operiert worden sei. Eventuell hätten die Ärzte in A._ das Honorar für die Operation der Ehefrau und für seine eigene Behandlung selber einkassiert. Vermutlich seien beide aus diesem Grund nicht in das Spitalregister eingetragen worden. Er habe der Beschwerdegegnerin eine notarielle Beglaubigung über die betreffenden Rechnungen zukommen lassen; dabei seien ihm zusätzliche Kosten von EUR 150.- entstanden.
Der Krankenpflegeversicherer gibt vernehmlassungsweise an, notariell beglaubigte Rechnungen lägen ihm keine vor. Er lehne die Kostenerstattung und damit die Leistungspflicht für die in Frage stehende Behandlungen weiterhin ab.
3. 3.1 Das Administrativverfahren wie auch der kantonale Sozialversicherungsprozess sind vom Untersuchungsgrundsatz beherrscht (Art. 43 Abs. 1 und Art. 61 lit. c ATSG). Danach haben die Kasse und das Sozialversicherungsgericht den rechtserheblichen Sachverhalt von Amtes wegen festzustellen. Diese Untersuchungspflicht dauert so lange, bis über die für die Beurteilung des streitigen Anspruchs erforderlichen Tatsachen hinreichende Klarheit besteht. Das Untersuchungsprinzip weist einen engen Bezug zum Grundsatz der freien Beweiswürdigung auf. Führen die im Rahmen des Untersuchungsgrundsatzes von Amtes wegen vorzunehmenden Abklärungen den Versicherungsträger oder das Gericht bei umfassender, sorgfältiger, objektiver und inhaltsbezogener Beweiswürdigung (<ref-ruling> E. 4.1 S. 400) zur Überzeugung, ein bestimmter Sachverhalt sei überwiegend wahrscheinlich (<ref-ruling> E. 5b S. 360 mit Hinweisen) und es könnten weitere Beweismassnahmen an diesem feststehenden Ergebnis nichts mehr ändern, so bedeutet der Verzicht auf die Abnahme weiterer Beweise keine Verletzung des Anspruchs auf rechtliches Gehör (antizipierte Beweiswürdigung). Bleiben jedoch erhebliche Zweifel an Vollständigkeit und/oder Richtigkeit der bisher getroffenen Tatsachenfeststellung bestehen, ist weiter zu ermitteln, solange von zusätzlichen Abklärungsmassnahmen noch neue wesentliche Erkenntnisse zu erwarten sind (Urteil 8C_364/2007 vom 19. November 2007 E. 3.2).
3.2 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (Art. 105 Abs. 1 und 2 BGG). Der Untersuchungsgrundsatz ergibt sich wie erwähnt aus Bundesrecht (vgl. <ref-law>). Hat das kantonale Gericht die rechtserheblichen tatsächlichen Feststellungen unter Verletzung des Untersuchungsgrundsatzes getroffen - oder sind sie als solche offensichtlich unrichtig -, so ist das Bundesgericht demnach nicht daran gebunden.
4. 4.1 Dem Beschwerdeführer gelingt es nicht aufzuzeigen, inwiefern die von der Vorinstanz namhaft gemachten Feststellungen offensichtlich unrichtig sein sollten. Zwar legt die in der Stellungnahme eines Belegarztes im Spital X._, wo am 23. Februar 2007 eine Abdominalplastik vorgenommen wurde, enthaltene, etwas gewundene Ausdrucksweise ("Es wurde kein Mesh eingesetzt und dies würde auch nicht den mir bekannten Voroperationen entsprechen") nicht ohne Weiteres nahe, der vorgängige Einsatz eines Netzes in das Abdomen sei geradezu ausgeschlossen (so aber der angefochtene Entscheid, S. 5 unten). Auch stellt die unterschiedliche Erscheinungsform der handschriftlichen Signatur eines Arztes insoweit kein besonders starkes Indiz dar, als es sich einmal um eine Vollunterschrift und einmal um ein blosses Visum zu handeln scheint. Die Begebenheiten sprechen indessen insgesamt doch gegen eine - durch erstattungsfähige Barzahlung entgoltene - Spitalbehandlung in A._. Die diesbezüglichen Erwägungen des kantonalen Gerichts sind anhand der Akten nachvollziehbar. Angefügt sei, dass die im Vergleich von Briefkopf und Stempel mehrfach verzeichnete Diskrepanz bezüglich Ort und Bezeichnung des sowohl den Beschwerdeführer wie auch dessen Ehefrau behandelnden Spitals nicht etwa dadurch erklärbar ist, dass es sich um verschiedene Zweige derselben organisatorischen Einheit handelt; S._ und K._ sind zwei verschiedene, über dreissig Kilometer voneinander entfernte Städte. Wenn es sich beim "Zentrum S._" lediglich um eine zentrale Krankenhausorganisation handeln würde, hätten die vor Ort abklärenden Stellen auf diese Besonderheit aufmerksam gemacht. Im Weiteren ist nicht einsehbar, weshalb der Beschwerdeführer, der eine umfangreiche Dokumentation zum Fall in das Verfahren eingebracht hat, im Wissen um den Rechtsstreit ausgerechnet von einer eigens eingeholten notariellen Beglaubigung über die Echtheit beweisender Dokumente keine Kopie angefertigt haben soll. Im Übrigen kann es mit einer Verweisung auf die Ausführungen im angefochtenen Entscheid sein Bewenden haben, zumal sich der Beschwerdeführer nur teilweise mit den dort dargestellten Gesichtspunkten auseinandersetzt.
4.2 Der Entscheid des kantonalen Gerichts genügt den Erfordernissen des Untersuchungsprinzips (oben E. 3.1). Die Vorinstanz durfte mithin ohne weitere Abklärungen darauf erkennen, es sei unwahrscheinlich, dass sich der anspruchserhebliche Sachverhalt tatsächlich verwirklicht habe. Der Beschwerdeführer zeigt die Möglichkeit auf, dass eine erfolgte Barzahlung nicht bestimmungsgemäss verbucht worden sein könnte. Die beschriebenen Unstimmigkeiten lassen sich aber nur unzureichend durch eine solche Hypothese erklären. Sie belegen zwar auch nicht abschliessend, dass die eingereichten Dokumente über Spitalbehandlungen in A._ unecht und/oder in ihrer inhaltlichen Aussage unwahr sind; insgesamt bestehen aber derart grosse Zweifel an ihrer Beweiskraft, dass die fraglichen Behandlungen jedenfalls nicht als überwiegend wahrscheinlich erfolgt gewertet werden können. Da der Beschwerdeführer die materielle Beweislast für das Vorliegen dieser Leistungsvoraussetzung trägt (<ref-law>; <ref-ruling> E. 5.5 S. 216), gilt diese als nicht erstellt. Die Beschwerdegegnerin hat ihre Leistungspflicht zu Recht verneint.
5. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1). Die Abweisung des Rechtsmittels erfolgt aufgrund der beweisrechtlichen Lage; die Frage, ob die eingereichten Belege tatsächlich gefälscht sind, wie die Beschwerdegegnerin meint, muss (und kann wohl auch) nicht beantwortet werden. In Anbetracht der nicht einfachen Beweislage ist die unentgeltliche Prozessführung im Sinne der Befreiung von den Verfahrenskosten (<ref-law>) zu gewähren. Die entsprechenden Voraussetzungen sind erfüllt (<ref-ruling> E. 4a S. 202 und 371 E. 5b S. 372). Nach <ref-law> wird die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerden werden abgewiesen.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von insgesamt Fr. 500.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Gesundheit schriftlich mitgeteilt.
Luzern, 28. Mai 2009
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Meyer Traub