Fatti:
A. Il dott. S._, cittadino svizzero nato nel 1932, domiciliato a B._, è stato, durante gli anni dal 1963 al 1997, funzionario presso il Consiglio d'Europa a Strasburgo e, in quanto tale, assicurato contro le malattie, unitamente alla moglie, presso la Van Breda & Co. International di Anversa.
L'8 ottobre 2001, l'interessato ha presentato all'Ufficio assicurazione malattia del Cantone Ticino un'istanza volta all'esonero dall'obbligo assicurativo in Svizzera, facendo valere ch'egli, nella sua qualità di pensionato del Consiglio d'Europa, sarebbe rimasto sempre assicurato presso la Van Breda International.
L'Ufficio cantonale ha respinto, per decisione 31 ottobre 2001, la domanda di esonero per carenza dei presupposti legali e ha fissato l'inizio teorico dell'obbligo assicurativo al 1° luglio 1999, imponendo ai coniugi S._ di iscriversi presso un assicuratore riconosciuto e autorizzato all'esercizio entro il termine di 30 giorni.
Statuendo su reclamo il 7 dicembre 2001, l'amministrazione ha confermato la propria precedente decisione.
B. Per giudizio 7 maggio 2002, il Tribunale delle assicurazioni del Cantone Ticino ha respinto il gravame interposto dall'interessato, tramite l'avv. Gianora, nel senso che ha tutelato il provvedimento amministrativo impugnato, rilevando anch'esso che non erano adempiute, in concreto, le condizioni di esonero dall'obbligo di assicurazione.
C. Sempre assistito dall'avv. Gianora, S._ interpone al Tribunale federale delle assicurazioni un ricorso di diritto amministrativo con cui ribadisce, unitamente alla moglie, la richiesta di esonero dall'obbligo di assicurazione delle cure medico-sanitarie ai sensi del diritto svizzero.
L'amministrazione e l'Ufficio federale delle assicurazioni sociali, divisione malattia e infortuni, dal 1° gennaio 2004 integrata nell'Ufficio federale della sanità pubblica, hanno rinunciato a formulare delle osservazioni in merito al gravame.
D. Interpellati per una presa di posizione in una fase successiva della procedura, il Dipartimento federale degli affari esteri, per il tramite della Direzione delle risorse e della rete esterna, e l'Ufficio federale della sanità pubblica hanno espresso la propria opinione sul tema in discussione.

Diritto:
1. Oggetto della presente lite è il tema dell'assoggettamento dei coniugi S._ all'obbligo di affiliazione a una cassa malati riconosciuta e autorizzata all'esercizio dalla data del loro rientro in Svizzera e, meglio, dal 1° luglio 1999, come stabilito dall'Ufficio assicurazione malattia del Cantone Ticino.
2. 2.1 La decisione amministrativa impugnata è stata emanata precedentemente all'entrata in vigore (1° giugno 2002) dell'Accordo del 21 giugno 1999 tra la Confederazione Svizzera, da una parte, e la Comunità europea ed i suoi Stati membri, dall'altra, sulla libera circolazione delle persone. Questo Accordo, in particolare il suo Allegato II, che regola il coordinamento dei sistemi di sicurezza sociale, non si applica pertanto nella presente procedura (<ref-ruling>).
Medesimo discorso vale, per quanto riguarda il diritto interno svizzero, per la Legge federale sulla parte generale del diritto delle assicurazioni sociali (LPGA) del 6 ottobre 2000, entrata in vigore il 1° gennaio 2003, quindi anch'essa posteriormente alla data decisiva del provvedimento in lite (<ref-ruling> consid. 1, 121 V 366 consid. 1b).
2.2 Qualora, come in concreto, la lite non verta sull'assegnazione o il rifiuto di prestazioni assicurative, il Tribunale federale delle assicurazioni deve limitarsi ad esaminare se il giudizio di primo grado abbia violato il diritto federale, compreso l'eccesso o l'abuso del potere d'apprezzamento, oppure se l'accertamento dei fatti sia manifestamente inesatto, incompleto od avvenuto violando norme essenziali di procedura (art. 132 OG in relazione con gli art. 104 lett. a e b e 105 cpv. 2 OG).
3. La Corte cantonale ha rettamente rilevato che, giusta l'<ref-law>, ogni persona domiciliata in Svizzera deve assicurarsi o farsi assicurare dal proprio rappresentante legale per le cure medico-sanitarie entro tre mesi dall'acquisizione del domicilio o dalla nascita in Svizzera. Per il cpv. 2 della stessa norma il Consiglio federale può prevedere tuttavia eccezioni all'obbligo d'assicurazione, segnatamente per i dipendenti di organizzazioni internazionali e di Stati esteri.
Sulla base di questa delega l'autorità esecutiva federale ha emanato l'<ref-law>, il cui cpv. 3 dispone che gli ex funzionari di organizzazioni internazionali come pure i loro familiari ai sensi dell'<ref-law> sono, a domanda, esentati dall'obbligo d'assicurazione se beneficiano, per le cure in Svizzera, di una copertura assicurativa equivalente presso l'assicurazione malattie della loro primitiva organizzazione.
3.1 La legge è da interpretare in primo luogo procedendo dalla sua lettera. Se il testo di un disposto legale è chiaro e non sia pertanto necessario far capo ad altri metodi d'interpretazione ai fini di appurarne la portata, è lecito scostarsi dal senso letterale soltanto qualora conduca a soluzioni manifestamente insostenibili, contrarie alla volontà del legislatore. Tuttavia, se il testo non è perfettamente chiaro, se più interpretazioni del medesimo sono possibili, dev'essere ricercato quale sia la vera portata della norma, prendendo in considerazione tutti gli elementi d'interpretazione, in particolare lo scopo della disposizione, il suo spirito, nonché i valori su cui essa prende fondamento. Pure di rilievo è il senso che essa assume nel suo contesto (<ref-ruling> consid. 3.1, 356 consid. 3.3, 129 V 103 consid. 3.2, 165 consid. 3.5, 263 consid. 5.1, 284 consid. 4.2 e riferimenti).
3.2 Interpretando l'<ref-law>, succitato, la Corte cantonale ha ritenuto, in sostanza, che la norma ha per scopo di permettere al funzionario di un'organizzazione internazionale con sede in Svizzera di continuare a beneficiare, unitamente ai suoi familiari, dell'esenzione dall'obbligo assicurativo, prevista dal primo capoverso del medesimo disposto, quando questi cessa di essere attivo e si trattenga in territorio elvetico. Pur non essendo esplicitata dalla norma, la restrizione territoriale alle organizzazioni con sede in Svizzera è, a mente dei primi giudici, doverosa, non potendo la legislazione nazionale regolare i rapporti assicurativi relativi al personale di organizzazioni internazionali aventi la loro sede all'estero.
3.3 Il Tribunale federale delle assicurazioni dissente dall'opinione dei primi giudici. Già si è detto in precedenza di come l'autorità esecutiva federale, facendo uso della competenza conferitale dall'<ref-law>, abbia emanato l'<ref-law>, il cui cpv. 1 dispone che i membri delle missioni diplomatiche, delle missioni permanenti e delle sedi consolari in Svizzera come pure gli impiegati di organizzazioni internazionali e i corrispettivi familiari che li accompagnano non sono soggetti all'obbligo d'assicurazione. Per la seconda frase del medesimo capoverso essi sono soggetti all'assicurazione svizzera se ne fanno espressa domanda.
Dal chiaro tenore della norma emerge che il beneficio di un esonero dall'obbligo d'assicurazione viene fatto dipendere dalla sede in Svizzera per le sole missioni diplomatiche e consolari, mentre tale presupposto non è richiesto per le organizzazioni internazionali. La stessa distinzione vien fatta pure all'<ref-law>, che concerne il personale domestico dei membri delle missioni e degli impiegati di organizzazioni internazionali. Un trattamento differenziato dei membri delle missioni diplomatiche e consolari rispetto ai dipendenti di organizzazioni internazionali è parimenti previsto, infine, dall'<ref-law>, secondo il quale, come s'è visto, i soli ex funzionari di organismi internazionali, come pure i loro familiari, sono, a domanda, esentati dall'obbligo d'assicurazione se beneficiano, per le cure in Svizzera, di una copertura assicurativa equivalente presso l'assicurazione malattie della loro primitiva organizzazione.
3.4 Tale interpretazione è sostanzialmente condivisa sia dal Dipartimento federale degli affari esteri, sia dall'Ufficio federale della sanità pubblica, espressamente interpellati dal Tribunale federale delle assicurazioni per una presa di posizione. L'opinione di questa Corte non è inoltre contraddetta dai lavori preparatori della norma d'ordinanza in oggetto, prodotti dall'autorità di vigilanza nel corso della presente procedura. Nella misura, poi, in cui dalla giurisprudenza pubblicata in <ref-ruling> sull'obbligo assicurativo del figlio domiciliato in Svizzera di un impiegato di un'organizzazione internazionale domiciliato all'estero fosse implicitamente desumibile una diversa interpretazione da quella esposta al precedente considerando, la stessa non può essere seguita. Né si dimentichi che alle organizzazioni internazionali vengono accordati privilegi e immunità affinché possano esercitare le loro funzioni in modo indipendente e in piena libertà. È precisamente per assicurare tale indipendenza che dette organizzazioni hanno istituito un proprio regime di previdenza sociale (cfr. il Messaggio 13 settembre 1995 del Consiglio federale concernente gli scambi di lettere relativi allo statuto dei funzionari internazionali di cittadinanza svizzera riguardo alle assicurazioni sociali svizzere, FF 1995 IV 700).
Dato quanto precede, si deve concludere, contrariamente ai primi giudici, che la possibilità, prevista dall'<ref-law>, di domandare l'esonero dall'obbligo assicurativo non è riservata ai soli ex funzionari di organizzazioni internazionali aventi la loro sede in Svizzera.
4. Rimane ora da esaminare il tema dell'equivalenza della copertura assicurativa, per le cure in Svizzera, di cui beneficiano i coniugi S._ presso la Van Breda & Co. International di Anversa, assicuratrice contro le malattie dei funzionari e degli impiegati del Consiglio d'Europa a Strasburgo.
4.1 A titolo subordinato, la Corte cantonale si è pure chinata sulla questione dell'applicabilità dell'<ref-law>. Giusta tale norma, nella versione vigente sino al 31 maggio 2002, applicabile in concreto, a domanda, sono esentate dall'obbligo d'assicurazione le persone obbligatoriamente assicurate contro le malattie in virtù del diritto estero, se l'assoggettamento all'assicurazione svizzera costituirebbe un doppio onere e se esse beneficiano di una copertura assicurativa equivalente per le cure in Svizzera. Alla domanda va accluso un attestato scritto dell'organo estero competente che dia tutte le informazioni necessarie.
4.2 Senza chiarire più da vicino i temi del doppio onere e dell'equivalenza della copertura assicurativa estera, l'istanza precedente ha statuito non essere dati in concreto neppure i presupposti per concedere l'esenzione in base all'<ref-law>, in quanto l'insorgente, nonostante esplicito invito, non aveva prodotto attestato dal quale risultasse, con la necessaria chiarezza, che la protezione assicurativa presso la Van Breda International gli fosse obbligatoriamente imposta dal diritto pubblico straniero.
Viste le conclusioni che precedono, i primi giudici dovranno ora necessariamente appurare il tema dell'equivalenza della copertura assicurativa estera, esaminandolo dal profilo dell'<ref-law>. A questo proposito, la precedente istanza si atterrà segnatamente alle considerazioni sviluppate dal Tribunale federale delle assicurazioni sulla questione in oggetto nella sentenza del 4 ottobre 2001 in re T. (K 167/00).
5. Non trattandosi in concreto di una lite avente per oggetto l'assegnazione o il rifiuto di prestazioni assicurative, la procedura non è gratuita (art. 134 OG a contrario). Le spese processuali, che seguono la soccombenza, devono pertanto essere poste a carico dell'amministrazione opponente. Quest'ultima rifonderà inoltre all'insorgente, assistito da un legale, un'indennità per le spese ripetibili della sede federale (art. 156 e 159 in relazione con l'art. 135 OG).

Per questi motivi, il Tribunale federale delle assicurazioni pronuncia:
1. Il ricorso di diritto amministrativo è accolto nel senso che, annullato il giudizio impugnato del 7 maggio 2002, la causa è rinviata al Tribunale delle assicurazioni del Cantone Ticino affinché, previo complemento istruttorio conformemente ai considerandi, renda un nuovo giudizio.
2. Le spese giudiziarie, fissate in complessivi fr. 500.-, sono poste a carico dell'Ufficio assicurazione malattia del Cantone Ticino.
3. L'anticipo spese di fr. 500.- prestato dal ricorrente viene retrocesso.
4. L'amministrazione opponente verserà al ricorrente la somma di fr. 2'500.- (comprensiva dell'imposta sul valore aggiunto) a titolo di indennità di parte per la procedura federale.
5. La presente sentenza sarà intimata alle parti, al Tribunale cantonale delle assicurazioni, Lugano, all'Ufficio federale della sanità pubblica e al Dipartimento federale degli affari esteri.