Fatti:
A. A.a In seguito a un controllo, l'Ufficio dell'assicurazione malattia del Cantone Ticino (UAM) ha constatato agli inizi del 2008 che, malgrado li avesse informati al momento del rilascio del permesso G, oltre 10'000 lavoratori frontalieri italiani non avevano fatto uso della facoltà accordata loro dall'Accordo del 21 giugno 1999 tra la Comunità europea e i suoi Stati membri, da una parte, e la Confederazione Svizzera, dall'altra, sulla libera circolazione delle persone (ALC; RS 0.142.112.681) di esercitare il diritto di opzione in favore del Paese di residenza per la copertura delle cure medico-sanitarie ed essere di conseguenza esentati in Svizzera.
In considerazione dell'elevato numero di persone interessate e delle difficoltà da esse incontrate nel capire l'importanza (e le modalità) del diritto di opzione, l'autorità cantonale, d'intesa con quelle federali (Ufficio federale della sanità pubblica [UFSP] e Ufficio federale delle assicurazioni sociali [UFAS]), ha pertanto deciso nel giugno 2008 di "regolarizzare" questi lavoratori. Dopo avere ricordato che in presenza di "casi giustificati" l'ALC consente di riconoscere l'esenzione retroattiva anche alle richieste presentate dopo i tre mesi successivi all'obbligo di assicurarsi in Svizzera, l'amministrazione ha deciso di avviare una procedura in sanatoria e ha assegnato un periodo supplementare, di carattere unico e straordinario, scadente il 30 settembre 2008, per esercitare (nuovamente) il diritto di opzione. La misura è stata comunicata dal Consiglio di Stato mediante bollettino stampa del 3 giugno 2008. Inoltre, l'UAM ha pure avvisato personalmente, con comunicazione postale (non raccomandata) del 12 giugno 2008 inviata al loro recapito in Italia, i diretti interessati facendo presente che in assenza di una loro determinazione essi sarebbero stati obbligati ad assicurarsi in Svizzera e con loro ogni familiare non esercitante un'attività lavorativa. Con le medesime modalità sono infine stati informati anche i rispettivi datori di lavoro oltre a diverse organizzazioni sindacali ed altri enti.
A.b Con decisione del 17 febbraio 2009 e con effetto da tale data, l'UAM ha affiliato d'ufficio presso Helsana Assicurazioni SA D._, cittadino italiano residente in Italia, il quale dal mese di aprile 2005 lavora in qualità di muratore presso la ditta P._ SA di Lugano al beneficio di un permesso G per frontalieri. L'amministrazione ha adottato questo provvedimento dopo avere osservato che l'interessato aveva lasciato trascorrere infruttuosamente anche il termine di sanatoria del 30 settembre 2008 che gli era stato comunicato con lo scritto del 12 giugno 2008.
A.c Mediante reclamo del 25 febbraio 2009 D._ si è opposto a tale provvedimento. Facendo valere di non avere ricevuto la comunicazione del 12 giugno 2008 e di non essere stato informato nemmeno in altro modo, l'interessato, peraltro già coperto in Italia per le cure sanitarie, ha dichiarato di volere esercitare il diritto d'opzione in favore del sistema sanitario del suo Paese di residenza. Da parte sua, con provvedimento del 26 marzo 2009 l'UAM ha respinto il reclamo. Ritenendo di avere debitamente informato l'interessato per mezzo di una campagna di informazione capillare, che oltre i singoli lavoratori aveva pure coinvolto i datori di lavoro e gli organi di stampa - permettendo di "regolarizzare" oltre il 95 % dei frontalieri "inadempienti" -, l'amministrazione gli ha negato la possibilità di esercitare, fuori tempo limite, il diritto di opzione ed ha escluso l'esistenza di un (nuovo) "caso giustificato" ai sensi dell'ALC.

B. D._ è insorto al Tribunale delle assicurazioni del Cantone Ticino, il quale, compiuti alcuni accertamenti, ha confermato l'operato dell'amministrazione e respinto il ricorso dell'interessato (pronuncia del 9 novembre 2009). La Corte cantonale ha in sostanza dato atto all'UAM di avere adempiuto al proprio obbligo di informazione e ha escluso che la mancata trasmissione, per raccomandata, della comunicazione personale del 12 giugno 2008 potesse motivare un ulteriore "caso giustificato" ai sensi dell'ALC. Di conseguenza ha ritenuto tardiva l'opzione formulata da D._. Inoltre ha respinto, considerandola infondata, la censura di quest'ultimo in merito a una pretesa disparità di trattamento tra i frontalieri di nazionalità italiana (o di altri Paesi dell'Unione europea) che abitano in Italia e lavorano in Svizzera, nei confronti dei quali il termine di tre mesi per esercitare il diritto di opzione sarebbe applicato con rigore, e i frontalieri di nazionalità svizzera che vivono in Italia e lavorano in Svizzera, per i quali il termine di tre mesi verrebbe fatto decorrere dalla conoscenza effettiva del diritto d'opzione. Infine ha ricordato all'interessato la possibilità concessagli dall'<ref-law> di chiedere, datene le condizioni, il beneficio del sussidio per il pagamento dei premi, mentre, in assenza di una decisione impugnabile, non è entrata nel merito sulla possibilità di accedere a una franchigia più elevata o ad altri modelli assicurativi.
C. D._ si è aggravato al Tribunale federale al quale, in sintesi, chiede di annullare il giudizio impugnato e di attestargli l'avvenuto e regolare esercizio del diritto di opzione in favore del sistema sanitario italiano. In particolare ribadisce di non avere avuto notizia, prima della decisione di affiliazione d'ufficio del 17 febbraio 2009, della sanatoria messa in atto dalle autorità svizzere, né attraverso la comunicazione non raccomandata del 12 giugno 2008, mai pervenutagli, né per mezzo di un'informazione del suo datore di lavoro e neppure in altro modo. Domanda inoltre di essere posto al beneficio dell'assistenza giudiziaria parziale, nel senso di essere dispensato dal versamento (anticipato) delle presunte spese giudiziarie. Infine i suoi patrocinatori hanno chiesto - e ottenuto - la sospensione di una ventina di ricorsi da essi presentati a questa Corte sullo stesso tema in attesa di un giudizio finale nella presente causa.
Invitati ad esprimersi - tra l'altro sulla eventuale applicabilità, negata dagli Uffici interpellati, appoggiata per contro dal ricorrente, al caso di specie dell'art. 3 n. 3 del regolamento (CEE) n. 574/72 del Consiglio, del 21 marzo 1972, che stabilisce le modalità di applicazione del regolamento (CEE) n. 1408/71 relativo all'applicazione dei regimi di sicurezza sociale ai lavoratori subordinati, ai lavoratori autonomi e ai loro familiari che si spostano all'interno della Comunità (RS 0.831.109.268.11) e che regola segnatamente le modalità di comunicazione diretta tra istituzioni di uno Stato membro e persona che risiede o dimora nel territorio di un altro Stato membro -, l'UAM (ormai parzialmente integrato, per gli aspetti qui di interesse, nell'Ufficio dei contributi dell'Istituto cantonale delle assicurazioni sociali) attraverso la presa di posizione del 28 gennaio 2010 trasmessa per conoscenza al Tribunale cantonale e da quest'ultimo inoltrata al Tribunale federale, l'UFSP e l'UFAS propongono sostanzialmente la reiezione del gravame e la conferma del giudizio cantonale.
Diritto:
1. Il ricorso in materia di diritto pubblico può essere presentato per violazione del diritto, conformemente a quanto stabilito dagli art. 95 e 96 LTF. Il Tribunale federale applica d'ufficio il diritto (<ref-law>; cfr. tuttavia l'eccezione del cpv. 2) e non è pertanto vincolato né dagli argomenti sollevati nel ricorso né dai motivi addotti dall'autorità precedente. Per il resto, fonda la sua sentenza sui fatti accertati dall'autorità inferiore (<ref-law>). Può scostarsi da questo accertamento solo qualora esso sia avvenuto in modo manifestamente inesatto o in violazione del diritto ai sensi dell'<ref-law> (<ref-law>).
2. 2.1 L'ALC è entrato in vigore il 1° giugno 2002 ed è pacificamente applicabile al caso di specie sotto il profilo temporale.
Giusta l'art. 1 cpv. 1 dell'Allegato II ALC, elaborato sulla base dell'art. 8 ALC e facente parte integrante dello stesso (art. 15 ALC), in unione con la sezione A di tale allegato, le parti contraenti applicano nell'ambito delle loro relazioni in particolare il regolamento (CEE) n. 1408/71 del Consiglio, del 14 giugno 1971, relativo all'applicazione dei regimi di sicurezza sociale ai lavoratori subordinati, ai lavoratori autonomi e ai loro familiari che si spostano all'interno della Comunità (in seguito: regolamento n. 1408/71 [RS 0.831.109.268.1]), come pure il già citato regolamento (CEE) n. 574/72, oppure disposizioni equivalenti. Anche la LAMal rinvia, al suo art. 95a (lett. a), all'ALC e a questi due regolamenti di coordinamento. Per contro i due nuovi regolamenti (CEE) n. 883/2004 (GU L 200 del 7 giugno 2004) e 987/2009 (GU L 284 del 30 ottobre 2009), che hanno rimpiazzato i regolamenti n. 1408/71 e n. 574/72 e che sono applicabili nell'Unione europea dal 1° maggio 2010, non sono ancora validi nelle relazioni tra la Svizzera e gli Stati membri dell'UE (comunicazione UFSP agli assicuratori e ai governi cantonali del 30 aprile 2010).
2.2 La regolamentazione poc'anzi menzionata è applicabile alla fattispecie in esame pure da un punto di vista personale e materiale. Di cittadinanza italiana, il ricorrente è infatti un lavoratore che è o è stato soggetto alla legislazione di uno o più Stati membri (art. 2 n. 1 del regolamento n. 1408/71). Inoltre l'oggetto del contendere riguarda l'applicazione di legislazioni (sul concetto v. art. 1 lett. j del regolamento n. 1408/71) relative a uno dei rischi enumerati espressamente all'art. 4 n. 1 del regolamento n. 1408/71, e più precisamente alla sua lettera a (prestazioni di malattia e di maternità; cfr. <ref-ruling> consid. 4.2 pag. 343; <ref-ruling> consid. 2.2 pagg. 204 seg.; Guylaine Riondel Besson, La sécurité sociale des travailleurs frontaliers dans le cadre de l'Accord sur la libre circulation des personnes, signé entre la Suisse et la Communauté européenne: l'exemple de l'assurance-maladie maternité [più in seguito: La sécurité sociale des travailleurs frontaliers], in Cahiers genevois et romands de sécurité sociale, 30/2003, pag. 28).
2.3 Trattandosi di una fattispecie internazionale, occorre in primo luogo stabilire il diritto applicabile.
2.3.1 Il titolo II del regolamento n. 1408/71 (art. 13-17bis) contiene alcune regole per la risoluzione della questione. L'art. 13 n. 1 enuncia il principio dell'unicità della legislazione applicabile in funzione delle regole previste dagli art. 13 n. 2-17bis, dichiarando determinanti le disposizioni di un solo Stato membro (cfr. pure Guylaine Riondel Besson, op. cit., pag. 20). Salvo eccezioni, il lavoratore subordinato è soggetto alla legislazione del suo Stato di occupazione salariata, anche se risiede sul territorio di un altro Stato membro o se l'impresa o il datore di lavoro da cui dipende ha la propria sede o il proprio domicilio nel territorio di un altro Stato membro. Il lavoratore frontaliere è dunque soggetto, in virtù di questo principio, alla legislazione dello Stato in cui lavora (principio della lex loci laboris); lo Stato competente è lo Stato di impiego (art. 13 n. 2 lett. a del regolamento n. 1408/71; <ref-ruling> consid. 4.3.1 pag. 343; <ref-ruling> consid. 6.1 pag. 143 con riferimenti).
2.3.2 Sono però possibili eccezioni a questo principio. In effetti, in applicazione dell'art. 89 del regolamento n. 1408/71, l'Allegato VI dello stesso regolamento indica le modalità particolari di applicazione delle legislazioni di alcuni Stati membri. Questo allegato è stato completato dalla Sezione A dell'Allegato II ALC "Coordinamento dei sistemi di sicurezza sociale", da cui risulta che le persone soggette alle disposizioni di legge svizzere possono, su domanda, essere esentate dall'assicurazione obbligatoria (LAMal) per tutto il tempo in cui risiedono in uno dei seguenti Stati e dimostrano di beneficiare di una copertura in caso di malattia: Germania, Austria, Francia, Italia e, in alcuni casi, Finlandia e Portogallo (Allegato II, Sezione A cpv. 1 lett. o cifra 3 b, nella sua versione modificata dalle decisioni n. 2/2003 e 1/2006 del Comitato misto UE-Svizzera del 15 luglio 2003 e del 6 luglio 2006 [RU 2004 1277 e RU 2006 5851]). Tale facoltà è comunemente detta "diritto d'opzione" (<ref-ruling> consid. 4.3.2 pag. 344 con riferimenti; sull'origine e la portata pratica di questo diritto d'opzione cfr. Riondel Besson, op. cit., pag. 24 e Ursula Hohn, Rechtsprobleme bei der Umsetzung des Koordinationsrechts in der Krankenversicherung, in: Thomas Gächter [ed.], Das europäische Koordinationsrecht der sozialen Sicherheit und die Schweiz, 2006, pagg. 66 seg.).
2.3.3 In virtù di questo diritto di opzione, le persone residenti in Italia e che lavorano in Svizzera possono scegliere se assicurarsi - insieme ai familiari senza attività lavorativa - in Svizzera secondo il regime di assicurazione malattia della LAMal oppure in Italia secondo il sistema sanitario nazionale italiano. L'eventuale esenzione dall'obbligo di assicurazione in Svizzera deve però essere chiesta con una domanda che va presentata alla competente autorità cantonale in materia di assicurazione malattia del luogo di lavoro entro i tre mesi successivi all'obbligo di assicurarsi in Svizzera (Allegato II, Sezione A cpv. 1 lett. o cifra 3 b aa e bb; Gebhard Eugster, Krankenversicherung, in Soziale Sicherheit, SBVR, 2a ed. 2007, pag. 423, n. 73 e 75; Guylaine Riondel Besson, Le droit d'option en matière d'assurance maladie dans le cadre de l'accord sur la libre circulation des personnes : difficultés de mise en oeuvre et conséquences pour les assurés [in seguito: Le droit d'option], in : Cahiers genevois et romands de sécurité sociale, 42/2009, pag. 35; Bettina Kahil-Wolff/Corinne Pacifico, Sécurité sociale, droit du travail et fiscalité: le droit applicable en cas de situations transfrontalières, in: Assujettissement, cotisations et questions connexes selon l'Accord sur la libre circulation des personnes CH-CE, 2004, pag. 37). Per i lavoratori frontalieri, detto termine comincia a decorrere dal primo giorno di lavoro (Riondel Besson, Le droit d'option, op. cit., pag. 35).
2.3.4 Nel caso di specie è pacifico che il ricorrente, che ha iniziato la sua attività lavorativa di frontaliere in Svizzera nel 2005, non ha presentato alcuna domanda nel termine di tre mesi dall'obbligo di assicurarsi in Svizzera. Ciò significa che in circostanze normali egli sarebbe automaticamente soggetto al diritto svizzero e non potrebbe più prevalersi della facoltà di esenzione concessagli dalle suesposte disposizioni convenzionali (cfr. Riondel Besson, Le droit d'option, op. cit., pag. 35). Ci si potrebbe, è vero, ancora domandare se l'omessa domanda di esenzione entro i termini stabiliti dall'ALC non fosse eventualmente riconducibile a una inadempienza da parte delle autorità cantonali preposte all'obbligo di informazione (<ref-law> e <ref-law>), come sembra insinuare anche in questa sede l'insorgente con riferimento al verbale di udienza del 25 settembre 2009 e all'affermazione ivi fatta secondo cui egli non avrebbe ricevuto alcuna informazione relativa al diritto di opzione né quando aveva cominciato a lavorare per P._ SA nel 2005 né al momento della procedura di sanatoria. Tuttavia, la questione, già sufficientemente approfondita dai primi giudici, i quali hanno peraltro ricostruito le modalità di trasmissione, insieme al permesso G e a una lettera esplicativa dell'UAM, del modulo ufficiale TI1 per la verifica della copertura assicurativa contro le malattie del lavoratore frontaliere residente in uno Stato della Comunità europea, in Norvegia o in Islanda e dei familiari senza attività lavorativa (v. verbale di audizione 17 giugno 2009 del responsabile del servizio della cancelleria della sezione dei permessi e dell'immigrazione del Cantone Ticino, V._), non necessita di ulteriore disamina poiché con la successiva messa in atto della procedura in sanatoria, che ha riaperto un nuovo termine di tre mesi per esercitare il diritto di opzione, essa ha di fatto perso la sua rilevanza pratica.
3. 3.1 Per quanto accertato in maniera vincolante e in conformità alle tavole processuali dall'istanza precedente, gli organi esecutivi (cantonali e federali) della LAMal - preso atto delle difficoltà incontrate dai lavoratori frontalieri italiani nel comprendere ed esercitare il diritto di opzione come pure dell'enorme mole di lavoro e dei rischi di incasso che l'affiliazione d'ufficio di così tante persone avrebbe comportato per il Cantone Ticino e gli assicuratori - hanno cercato una soluzione che permettesse loro di "regolarizzare" la posizione dei molti lavoratori frontalieri inadempienti. Sollecitato in tal senso dall'UAM, l'UFSP ha allora ricordato all'autorità cantonale che l'assegnazione, in casi giustificati, di un termine straordinario per l'esercizio del diritto di opzione corrisponde alla soluzione prevista dall'Allegato II ALC, quest'ultimo alla sua Sezione A cpv. 1 lett. o cifra 3 b aa seconda frase disponendo che quando in casi giustificati la richiesta è presentata dopo il termine di tre mesi, l'esenzione diventa efficace dall'inizio dell'assoggettamento all'assicurazione obbligatoria. In tali circostanze, come constatato dalla Corte cantonale, l'UFSP ha dato, insieme all'UFAS, il proprio benestare per una procedura in sanatoria.
Così, oltre al già ricordato bollettino stampa 3 giugno 2008 del Consiglio di Stato, le autorità cantonali hanno inviato il 12 giugno 2008 a oltre 12'600 lavoratori frontalieri, che non avevano fatto uso del diritto di opzione, una lettera personale in cui li si avvisava della possibilità di compilare l'allegato modulo TI1 e di ritornarlo a mezzo di una busta - anch'essa allegata e già provvista di indirizzo - entro il 30 settembre 2008 (termine supplementare di tre mesi, unico e straordinario), con la precisazione che se non vi avessero dato seguito sarebbero stati obbligati ad assicurarsi in Svizzera e con loro ogni familiare non esercitante un'attività lavorativa. Oltre a ciò, sempre in virtù degli accertamenti vincolanti operati dai giudici di prime cure, l'amministrazione ha pure trasmesso una comunicazione specifica a 13'569 datori di lavoro - anch'essi incaricati, in virtù del diritto cantonale di applicazione (v. <ref-law> e <ref-law>), di fornire ai lavoratori non domiciliati soggetti all'obbligo di assicurazione le informazioni necessarie (art. 16 della legge cantonale di applicazione della LAMal del 26 giugno 1997 [LCAMal; RL/TI 6.4.6.1] e art. 5 del relativo regolamento esecutivo [RLCAMal; RL/TI 6.4.6.1.1]) -, ha informato 11 sindacati ed ha coinvolto 8 enti vari con spettro d'azione allargato (Camera di Commercio, Ticino Turismo, Associazione Industrie Ticinesi [AITI], Associazione ticinese dei Giornalisti, Unione contadini ticinesi e Segretariato agricolo, Hotelleriesuisse Ticino, Società svizzera impresari costruttori [SSIC TI], Gastroticino). Infine, l'allora capo dell'UAM, C._, avrebbe rilasciato numerose interviste - non agli atti -, in cui avrebbe indicato i passi da intraprendere per esercitare il diritto di opzione. L'operazione ha permesso di "regolarizzare" il 95.8 % dei frontalieri interessati che hanno optato in favore della copertura assicurativa nel proprio Paese di residenza. Da verificare rimane per contro la situazione di diversi lavoratori che, al pari del qui ricorrente, lamentano di non avere ricevuto alcuna comunicazione (personale, tramite il datore di lavoro o in altro modo) prima della loro affiliazione d'ufficio alla LAMal.
3.2 Il Tribunale cantonale delle assicurazioni ha esaminato la vertenza alla luce dell'<ref-law> - concernente l'obbligo di informazione e di consulenza degli assicuratori e degli organi esecutivi delle singole assicurazioni sociali - e ha concluso che l'UAM aveva ampiamente adempiuto ai propri obblighi, come del resto ritenuto anche dall'UFSP e dall'UFAS. Trasponendo per analogia al caso di specie i principi elaborati dal Tribunale federale delle assicurazioni in RAMI 2004 n. U 517 pag. 428 (U 255/03) e facendo segnatamente leva sul principio della responsabilità individuale (<ref-law>) dei lavoratori interessati come pure sul fatto che i cittadini comunitari dovrebbero essere a conoscenza dei principi generali che reggono il diritto comunitario e quindi anche sull'aspetto che il diritto di opzione costituisce una eccezione all'affiliazione al luogo di lavoro, la Corte cantonale ha in particolare indicato che la pretesa ignoranza della legge - che era stata invocata da molti dei lavoratori frontalieri che hanno impugnato la decisione di affiliazione d'ufficio - nonché l'asserita mancata informazione diretta tramite raccomandata non costituivano palesemente un caso giustificato e non impedivano che l'opzione formulata il 25 febbraio 2009 dal ricorrente fosse tardiva.
3.3 Per parte sua, il ricorrente ribadisce in particolare l'assenza di una informazione personale che non sarebbe avvenuta né con la comunicazione del 12 giugno 2008 - mai pervenutagli - né in altra forma o tramite il datore di lavoro. In merito alla trasmissione della lettera del 12 giugno 2008 osserva che l'amministrazione non è stata in grado di dimostrarne l'avvenuto recapito e sottolinea la leggerezza di cui essa si sarebbe resa responsabile poiché, pur dovendo essere a conoscenza del (notorio) disservizio del sistema postale italiano, non si sarebbe preoccupata di inviarla per raccomandata. Aggiunge che la decisione di sanatoria avrebbe fatto sorgere in capo a tutti i destinatari un diritto soggettivo di cui dovevano necessariamente essere messi a conoscenza. Sennonché la comunicazione, qualificabile quale atto amministrativo, e più precisamente quale decisione (di portata generale), non essendo stata validamente notificata, sarebbe gravemente viziata. Vizio che non potrebbe di conseguenza cagionargli pregiudizio alcuno. Quanto alla esistenza di ulteriori canali informativi, l'insorgente osserva che questi non lo avrebbero raggiunto perché, a differenza dei frontalieri di cittadinanza svizzera residenti in Italia e attivi professionalmente in Svizzera - nei confronti dei quali l'amministrazione cantonale si dimostrerebbe assai più flessibile facendo partire il termine di tre mesi per esercitare l'opzione dalla loro conoscenza effettiva del diritto -, il frontaliere italiano conosce ben poco o nulla della realtà svizzera né legge o segue i giornali e i notiziari locali. Chiede pertanto, onde evitare ingiustificate disparità di trattamento, che la stessa flessibilità venga applicata anche nei suoi confronti e che gli venga dunque concesso un termine di grazia per esercitare finalmente il diritto d'opzione. Contesta inoltre la proporzionalità della misura che in sostanza non sarebbe né nell'interesse dei frontalieri italiani, che già godono di una copertura sanitaria (gratuita) in Italia, né nell'interesse del contribuente ticinese che in molti casi - tenuto conto dei salari normalmente modesti conseguiti dai frontalieri e degli elevati premi di assicurazione malattia a loro applicati in Svizzera (sul tema cfr. Hohn, op. cit., pagg. 66 seg.) - verrebbe chiamato a sovvenzionarne il pagamento attraverso il sistema del sussidiamento concesso anche agli assicurati residenti nella Comunità europea (v. <ref-law>). Infine ricorda come il Consiglio federale, rispondendo il 2 settembre 2009 a un'interpellanza (n. 09.3596) del Consigliere nazionale Meinrado Robbiani, abbia dato atto dell'elasticità con la quale la maggior parte dei Cantoni applicherebbe il termine di tre mesi per chiedere l'esenzione dall'obbligo assicurativo in Svizzera e come, tenuto conto delle difficoltà incontrate soprattutto dai frontalieri residenti in Italia, l'Esecutivo federale starebbe verificando la possibilità di negoziare una procedura speciale che vada maggiormente incontro alle loro esigenze (http://www.parlament.ch).
4. Per potere stabilire se il ricorrente ha effettivamente perso la facoltà di esercitare in sanatoria il diritto d'opzione poiché fatto valere tardivamente, ossia dopo il 30 settembre 2008, occorre dapprima esaminare se egli - circostanza contestata con il ricorso - è stato davvero messo in condizione di esercitarlo in tempo. Per rispondere a questa domanda occorre esaminare più da vicino la natura giuridica della misura adottata dall'UAM d'intesa con l'autorità federale di sorveglianza. Da questa valutazione, infatti, dipende anche quella successiva, relativa alla correttezza o meno della sua comunicazione/notifica. Mentre il Tribunale cantonale come pure l'opponente e gli uffici federali interpellati ritengono che la comunicazione della possibilità di sanare entro il 30 settembre 2008 le situazioni ancora aperte costituiva una semplice informazione, che (quantomeno per la Corte cantonale) non andava di per sé nemmeno notificata personalmente ai diretti interessati, per il ricorrente essa avrebbe invece fatto sorgere un diritto soggettivo che in quanto tale andava adeguatamente e personalmente notificato.
5. 5.1 Trattandosi di fattispecie internazionale, va subito premesso che, per prassi costante, la notifica all'estero di un documento ufficiale, quale può ad esempio essere un atto giudiziario oppure una decisione amministrativa, costituisce un atto d'imperio che, salvo disposizione convenzionale contraria o consenso dello Stato nel quale la notifica va effettuata, deve avvenire per via diplomatica o consolare (<ref-ruling> consid. 3a pag. 50 con riferimenti), a meno che non riguardi una comunicazione di natura meramente informativa senza effetti giuridici che in tal caso può essere direttamente notificata per posta (decreto K 18/04 del 18 luglio 2006 consid. 1.2; parere della Direzione del diritto internazionale pubblico del Dipartimento federale degli affari esteri [DFAE], in: GAAC 66/IV [2002] n. 128 pag. 1368). Il mancato rispetto di questi principi comporta una violazione della sovranità dello Stato estero e, quindi, del diritto internazionale pubblico (<ref-ruling> consid. 3b pag. 51; RDAT I-1993 n. 68 pag. 176 consid. 2b; decreto citato K 18/04 consid. 1.2 in fine).
5.2 Un atto è segnatamente qualificabile quale atto ufficiale se la sua notifica serve all'adempimento di un compito statale. Per la definizione di atto d'imperio non è per contro necessario che la sua notifica produca un pregiudizio immediato per il suo destinatario (parere della Direzione del diritto internazionale pubblico del DFAE, in: GAAC 65/II [2001] n. 71 pag. 761). Effetti giuridici esplica ad esempio anche l'assegnazione di un termine e la contestuale comminatoria di perenzione in caso di sua mancata osservanza (GAAC 66/IV [2002] n. 128 pag. 1368).
5.3 La notificazione irregolare di un atto amministrativo all'estero non esplica effetti giuridici e non può cagionare alcun pregiudizio al suo destinatario (<ref-ruling> consid. 3a. pag. 50 con riferimenti; sulla portata generale di questo principio cfr. Yves Donzallaz, La notification en droit interne suisse, 2002, n. 1115). È infatti solo con la sua comunicazione ufficiale alle parti che esso acquista esistenza giuridica. Fintanto che non è comunicato, l'atto non esiste (v. <ref-ruling>). Senza notificazione l'interessato non ha conoscenza del suo contenuto e non può prendere i provvedimenti necessari. La notificazione è pertanto indispensabile (cfr. pure Donzallaz, op. cit., n. 25, 141, 188). Anche in caso di diffida, il suo destinatario deve essere (direttamente e personalmente) informato sulle conseguenze alle quali si espone in caso di inosservanza del termine (o dell'ordine) impartito (cfr. per analogia RDAT II-1995 n. 58 pag. 152 consid. 3b; cfr. pure <ref-ruling> e sentenza del Tribunale federale delle assicurazioni H 224/04 del 28 aprile 2005 consid. 4.3 e 4.4).
5.4 Nell'ambito applicativo dell'ALC, il regolamento n. 1408/71 contempla agli art. 84-93 alcune norme di procedura amministrativa internazionale. Per l'art. 84 n. 3, ai fini dell'applicazione di detto regolamento, le autorità e le istituzioni degli Stati membri possono comunicare direttamente fra loro, nonché con le persone interessate o i loro mandatari. Da parte sua, l'art. 3 n. 3 del regolamento n. 574/72 stabilisce che le decisioni e altri documenti rilasciati da un'istituzione di uno Stato membro e destinati a persona che risiede o dimora nel territorio di un altro Stato membro possono essere notificati direttamente all'interessato per lettera raccomandata con ricevuta di ritorno. Tale disciplina mira ad eliminare alcuni ostacoli di natura tecnica ed amministrativa che potrebbero scoraggiare i lavoratori che intendono recarsi in altri Stati membri in cerca di un'occupazione. La notifica diretta da parte delle istituzioni della previdenza sociale agli interessati residenti in altri Stati membri, senza fare ricorso ad intermediario, cioè mediante il servizio postale, ha la funzione di semplificare le formalità amministrative e di accelerare lo svolgimento delle pratiche pur salvaguardando, con le forme previste, la certezza del diritto a favore degli interessati (sentenza della Corte di giustizia delle Comunità europee [CGCE] del 18 febbraio 1975 nella causa 66/74 Farrauto, Racc. 1975, pag. 157, punto 4; sulla rilevanza della giurisprudenza della CGCE ai fini interpretativi dell'ALC cfr. l'art. 16 cpv. 2 ALC [v. <ref-ruling> consid. 4.3.2 pag. 631 con riferimenti]).
5.5 Alla luce di quanto esposto ai consid. 5.1 e 5.2 appare evidente che per "decisioni e altri documenti" ai sensi dell'art. 3 n. 3 del regolamento n. 574/72 vanno intesi quegli atti che, senza espressa norma convenzionale, dovrebbero altrimenti essere trasmessi per via diplomatica per poter essere notificati validamente. Sono pertanto anche qui logicamente escluse da questa definizione le comunicazioni di carattere meramente informativo che non esplicano effetti giuridici.
5.6 Ora, se avuto riguardo alle indicazioni fornite dall'UAM al momento del rilascio del permesso G si può serenamente affermare che esse costituivano effettivamente delle semplici informazioni ai sensi degli <ref-law> e 10 OAMal perché si limitavano a ragguagliare i diretti interessati su diritti e obblighi direttamente risultanti dall'ALC, senza modificarli, non altrettanto si può sostenere in relazione a quanto avvenuto in occasione della sanatoria. Lo aveva del resto ben compreso inizialmente anche l'UAM allorché il 12 febbraio 2008 rivolgendosi all'UFSP ebbe modo di osservare che l'assegnazione di un termine supplementare avrebbe costituito un atto "extra legem". In effetti, la misura in sanatoria, modificando la situazione giuridica esistente e ristabilendo la facoltà di opzione convenzionalmente scaduta, ha chiaramente istituito un nuovo diritto, seppur vincolato - sotto comminatoria di sua nuova perenzione - al rispetto di un termine ben preciso. È quindi a torto che gli Uffici intervenuti contestano in sede di osservazioni al ricorso il carattere costitutivo della misura. Se da un lato è pur vero, come rilevano l'UFSP e l'UFAS, che la regolarizzazione straordinaria dei frontalieri - principalmente concessa per rendere loro un favore (v. a tal proposito Hohn, op. cit., pagg. 66 seg. e Istituto delle assicurazioni sociali, Accordo sulla libera circolazione delle persone e sicurezza sociale, in RDAT I-2002, pagg. 30 seg., i quali spiegano le molte ragioni che dovrebbero indurre questi lavoratori a optare per il loro sistema sanitario nazionale), ma non solo, perché, per quanto accertato dalla pronuncia impugnata (pag. 25), l'affiliazione d'ufficio di un così elevato numero di lavoratori avrebbe causato serie difficoltà pratiche e finanziarie all'amministrazione cantonale e agli assicuratori malattia (si pensi alle difficoltà di incasso [Hohn, op. cit., pag. 67, nota 16] e alla possibilità per questa cerchia di assicurati di richiedere ugualmente, datene le condizioni, una riduzione dei premi [<ref-law>]) - costituiva un atto unilaterale volontario, non dovuto, dall'altro la stessa non può certamente essere ridotta a una semplice comunicazione di natura meramente informativa priva di conseguenze giuridiche.
Già solo per questo motivo, il richiamo della Corte cantonale all'<ref-law> e alla giurisprudenza sviluppata nella sentenza U 255/03 non è calzante. In quella occasione si trattava infatti unicamente di statuire sull'obbligo dell'assicuratore infortuni di informare l'assicurato sulla possibilità, derivante direttamente dalla legge (<ref-law>), di stipulare un'assicurazione per accordo ("Abredeversicherung"). Per quanto appena esposto, la differenza tra le due situazioni è palese.
5.7 Né si potrebbe del resto - ipotesi, questa, invero nemmeno evocata dalle parti - considerare la decisione di sanatoria alla stregua di un'ordinanza amministrativa. Infatti, per definizione, un'ordinanza amministrativa è un'istruzione di servizio interna emanata dall'autorità superiore o di sorveglianza all'indirizzo di un'unità amministrativa incaricata dell'applicazione della legge nel caso concreto ed è tesa ad esplicitare l'interpretazione di una determinata disposizione di legge (o convenzionale) al fine di favorirne un'applicazione uniforme e garantire la parità di trattamento. Simile atto non ha forza di legge e non fonda quindi, di regola, direttamente diritti ed obblighi degli amministrati (donde, di principio, anche la sua inimpugnabilità diretta: v. <ref-ruling> consid. 4.3 pagg. 171 seg.; <ref-ruling>; cfr. pure sentenza 2C_105/2009 del 18 settembre 2009 consid. 6.4.1). Ora, anche alla luce del tenore delle comunicazioni dell'autorità cantonale, è evidente che con la decisione di sanatoria essa si è rivolta direttamente ai lavoratori frontalieri interessati concedendo loro nuovi diritti condizionati.
5.8 Scartata l'ipotesi della semplice informazione rispettivamente dell'ordinanza amministrativa, l'esatta natura del provvedimento può a questo punto rimanere indecisa perché in ogni caso - sia che si consideri la comunicazione del 12 giugno 2008 come una decisione individuale-concreta o diffida o come altro documento ai sensi dell'art. 3 n. 3 del regolamento n. 574/72 (contrariamente alla tesi sostenuta dall'UFAS, l'UAM, diversamente da un'autorità giudiziaria [<ref-ruling> consid. 2.2.3 pag. 295; decreto citato K 18/04 consid. 2.1.2 in fine], può senz'altro essere considerato un'istituzione ai sensi di tale disposto, trattandosi di un'autorità incaricata di applicare, almeno in parte, la legislazione in materia [art. 1 lett. n del regolamento n. 1408/71]), sia si voglia qualificare la sanatoria in quanto tale quale atto generale-astratto o generale-concreto (cfr. a tal proposito <ref-ruling> consid. 3.2 pag. 280; <ref-ruling> consid. 2a e b pagg. 316 seg.; Tobias Jaag, Die Abgrenzung zwischen Rechtssatz und Einzelakt, 1985, pagg. 29 segg., pagg. 183 segg.) -, la sostanza non muterebbe. Infatti, dal momento che la corretta notifica (o pubblicazione su un organo ufficiale [cfr. segnatamente l'<ref-law> in relazione con l'<ref-law> nonché l'art. 85 della Legge sul Gran Consiglio e sui rapporti con il Consiglio di Stato del 17 dicembre 2002, RL/TI 2.4.1.1, per il quale i regolamenti e i decreti esecutivi emanati dal Consiglio di Stato potrebbero entrare in vigore solo con la pubblicazione sul Bollettino ufficiale delle leggi e degli atti esecutivi]) dell'atto non è avvenuta o comunque non ha potuto essere dimostrata, esso non poteva esplicare effetti giuridici negativi (in casu: la perenzione del nuovo diritto di opzione) nei confronti del ricorrente (cfr. <ref-ruling>; <ref-ruling> consid. 4b pag. 8; <ref-ruling>; sentenze 2D_136/2007 del 19 giugno 2008 consid. 3.2, 2P.304/2005 del 14 marzo 2006, in RDAF 2007 I pag. 342, e 2P.83/2002 del 24 giugno 2003 consid. 2.3; sulla possibilità, in questi casi, di chiedere la restituzione di un termine omesso cfr. inoltre Donzallaz, op. cit., n. 1193).
5.9 Per quel che concerne più precisamente la notifica di una decisione o di una comunicazione dell'amministrazione, si ricorda che per giurisprudenza l'onere della prova incombe di massima all'autorità che intende trarne una conseguenza giuridica e che la circostanza deve perlomeno essere stabilita con il grado della verosimiglianza preponderante richiesto in materia di assicurazioni sociali (<ref-ruling> consid. 2b pag. 402; <ref-ruling> consid. 3b pag. 6; cfr. pure Donzallaz, op. cit., n. 1263 segg.). L'autorità sopporta pertanto le conseguenze dell'assenza di prova nel senso che se la notifica o la sua data sono contestate e se esistono effettivamente dubbi a tale proposito, ci si baserà sulle dichiarazioni del destinatario dell'invio (<ref-ruling> consid. 2.2 pag. 10; <ref-ruling> consid. 2a pag. 402 con riferimenti). La spedizione con la posta normale non consente in genere di stabilire se la comunicazione sia pervenuta al destinatario; la semplice presenza nel fascicolo della copia dell'invio non è sufficiente per dimostrare che tale lettera sia stata effettivamente spedita e ricevuta (<ref-ruling> consid. 1 pag. 8). Tuttavia, la prova della notifica di un atto può risultare da altri indizi o dall'insieme delle circostanze, quali la mancata protesta da parte di una persona che riceve dei richiami (cfr. <ref-ruling> consid. 3 pag. 46).
Nel caso di specie, l'UAM non è stato in grado di fornire la prova (secondo il grado della verosimiglianza preponderante) dell'avvenuta notifica della sua comunicazione nella sfera di influenza ("Machtbereich") del destinatario (v. sentenza 8C_621/2007 del 5 maggio 2008 consid. 4.2). Né la Corte cantonale, che ha persino escluso la sussistenza, per l'UAM, di un obbligo di informazione individuale e personale ai frontalieri (v. anche comunicazione del 1° febbraio 2010 del suo giudice delegato al Tribunale federale), ha ritenuto necessario approfondire oltre la questione tralasciando così in particolare di sentire il datore di lavoro del ricorrente, il quale, da parte sua, ancora in occasione dell'udienza del 25 settembre 2009 aveva categoricamente negato di essere stato informato, tramite la posta o P._ SA, sul diritto alla sanatoria. Di conseguenza ci si può e deve basare sulla dichiarazione dell'insorgente che sostiene di essere venuto a conoscenza di detta possibilità soltanto con la decisione di affiliazione d'ufficio del 17 febbraio 2009.
5.10 Un'interpretazione conforme al principio della buona fede impone alla parte toccata dalla notificazione viziata di agire entro un termine ragionevole dal momento in cui ha avuto conoscenza della comunicazione (sul tema v. anche Donzallaz, op. cit., n. 1203 segg.; più in generale sull'applicazione, in mancanza di disposizione specifica contraria, dei principi di procedura di diritto interno anche in ambito convenzionale cfr. <ref-ruling>). Ora, avendo prontamente reagito (il 25 febbraio 2009) dopo avere appreso (in seguito all'emanazione della decisione di affiliazione d'ufficio) della (nuova) possibilità di esercitare il diritto di opzione, il ricorrente non ha agito tardivamente. Egli poteva dunque validamente chiedere di essere esentato dall'obbligo assicurativo in Svizzera con effetto ex tunc, vale a dire dall'inizio del suo ipotetico assoggettamento (Allegato II ALC, Sezione A cpv. 1 lett. o cifra 3 b aa seconda frase).
5.11 Del resto, ad indiretta conferma di quanto precede si osserva - di transenna, trattandosi in buona parte di fatti nuovi che non sono stati accertati nella pronuncia impugnata - che le autorità cantonali sembrerebbero nel frattempo avere modificato la loro prassi. Nell'accogliere infatti il 21 aprile 2010 una mozione dell'11 marzo 2008 di Raoul Ghisletta, che chiedeva una moratoria nell'affiliazione retroattiva all'assicurazione malattia svizzera dei frontalieri che non avevano riempito (nel 2002) il modulo TI1, il Gran Consiglio ticinese, considerato evaso l'atto parlamentare per quel che concerneva la sanatoria scaduta il 30 settembre 2008 (oggetto delle presenti procedure di ricorso), ha ossevato che dall'ottobre 2008 si sarebbero registrati circa 1800 nuovi casi di frontalieri che non hanno esercitato il diritto di opzione. Ora, da una lettura del rapporto n. 6311R del 30 marzo 2010 della Commissione della gestione e delle finanze (consultabile al sito del Cantone Ticino http://www.ti.ch) sembrerebbe che l'autorità cantonale ha deciso una nuova procedura in sanatoria nei confronti di questi nuovi frontalieri ai quali, questa volta, è (stata) inviata per posta raccomandata la diffida a voler esercitare l'eventuale diritto di opzione.
6. 6.1 Per l'<ref-law>, introdotto in seguito all'entrata in vigore dell'ALC, a domanda, sono esentate dall'obbligo d'assicurazione - sancito dall'<ref-law> in combinazione con l'art. 1 cpv. 2 lett. d OAMal (v. DTF <ref-ruling> consid. 2.2.1 pag. 205) - le persone residenti in uno Stato membro della Comunità europea, purché possano esservi esentate conformemente all'ALC e al relativo Allegato II e dimostrino di essere coperte in caso di malattia sia nello Stato di residenza sia durante un soggiorno in un altro Stato membro della Comunità europea o in Svizzera.
Per quanto concerne la prima condizione, essa è soddisfatta per quanto appena visto. Relativamente al secondo requisito, l'ordinanza non prescrive forme particolari per fornire tale prova. Una dichiarazione scritta della competente autorità estera non è necessaria. Quale prova basta l'esibizione di un certificato di assicurazione che risponda ai requisiti del sistema di assicurazione malattia dello Stato di residenza (Gebhard Eugster, op. cit., pag. 426, n. 84; nello stesso senso pure l'UFSP nella sua lettera del 13 marzo 2008, pag. 2, all'UAM). Cosa che il ricorrente ha fatto, avendo già prodotto in sede di reclamo copia della tessera europea di assicurazione malattia rilasciata dalla Regione Lombardia.
6.2 Ne segue che il ricorso si dimostra fondato e che il giudizio impugnato come pure la decisione su reclamo dell'UAM devono essere annullati. In loro riforma (<ref-law>), al ricorrente va riconosciuta l'esenzione dall'assicurazione obbligatoria malattia in Svizzera.
6.3 Le spese giudiziarie seguono la soccombenza (<ref-law>) e andrebbero di principio poste a carico del Cantone Ticino poiché l'UAM (e in seguito l'Ufficio dei contributi) ha operato in qualità di organo cantonale di controllo dell'assicurazione malattia ai sensi dell'<ref-law> (cfr. sentenza 9C_182/2009 del 2 marzo 2010 consid. 8 con riferimento). Al Cantone, che ha agito nell'esercizio delle sue attribuzioni ufficiali, non possono però essere caricate spese giudiziarie (<ref-law>). Esso dovrà nondimeno rifondere al ricorrente, patrocinato da un'organizzazione sindacale, un'indennità per ripetibili della sede federale (<ref-law>). La domanda di assistenza giudiziaria del ricorrente è priva di oggetto.

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è accolto. Il giudizio del Tribunale delle assicurazioni del Cantone Ticino del 9 novembre 2009 e la decisione su reclamo dell'Ufficio cantonale dell'assicurazione malattia del 26 marzo 2009 sono annullati. Il ricorrente è esentato dall'obbligo di assicurazione malattia in Svizzera nel senso dei considerandi.
2. Non si prelevano spese giudiziarie.
3. Lo Stato del Cantone Ticino verserà al ricorrente la somma di fr. 2'000.- a titolo di indennità di parte per la procedura federale.
4. Il Tribunale delle assicurazioni del Cantone Ticino statuirà sulla questione delle spese ripetibili di prima istanza, tenuto conto dell'esito del processo in sede federale.
5. Comunicazione alle parti, al Tribunale delle assicurazioni del Cantone Ticino, all'Ufficio federale della sanità pubblica e all'Ufficio federale delle assicurazioni sociali.