Fatti:
A. Il 17 marzo 2006 il Presidente della Corte delle assise correzionali di Mendrisio ha condannato A._, cittadino italiano residente in Italia, alla pena di due anni di detenzione e all'espulsione dalla Svizzera per un periodo di sette anni, per complicità in rapina aggravata, complicità in rapina e atti preparatori punibili di rapina. L'interessato, detenuto dal 18 luglio 2005, è stato liberato condizionalmente il 16 novembre 2006.
B. Il 21 aprile 2006 l'Ufficio federale della migrazione ha pronunciato nei confronti di A._ un divieto d'entrata in Svizzera di durata illimitata in virtù dell'art. 13 cpv. 1 legge federale del 26 marzo 1931 concernente la dimora e il domicilio degli stranieri (LDDS; RS 142.20). Un suo ritorno in Svizzera è stato considerato indesiderato a motivo del suo comportamento (complicità in rapina aggravata e complicità in rapina; atti preparatori punibili di rapina) e per motivi di ordine e di sicurezza pubblici. La decisione è stata intimata all'interessato il 21 settembre 2006.
C. Con giudizio del 4 giugno 2008 il Tribunale amministrativo federale, Corte III (entrato in funzione il 1° gennaio 2007 e al quale la causa è stata trasmessa, cfr. art. 1 cpv. 1 e 53 cpv. 2 della legge del 17 giugno 2005 sul Tribunale amministrativo federale [LTAF; RS 173.32], in vigore dal 1° gennaio 2007 [RU 2006 1069]), ha respinto il ricorso esperito il 23 ottobre 2006 da A._ e ha confermato il provvedimento impugnato. Respinte le censure formali, la citata autorità ha considerato, in sintesi, che tenuto conto della pericolosità dell'insorgente e dell'elevato rischio di recidiva, il divieto d'entrata risultava giustificato nonché rispettoso del principio della proporzionalità.
D. L'11 luglio 2008 A._ ha presentato dinanzi al Tribunale federale un ricorso in materia di diritto pubblico, con cui chiede che la sentenza 4 giugno 2008 e la decisione 21 aprile 2006 siano annullate. Censura, in sostanza, una constatazione manifestamente inesatta ed arbitraria dei fatti, una violazione del suo diritto di essere sentito e della propria libertà personale nonché la disattenzione degli art. 3 ALC e 5 Allegato I ALC.
Chiamati ad esprimersi il Tribunale amministrativo federale, Corte III, ha rinunciato a formulare osservazioni, mentre l'Ufficio federale della migrazione, allineandosi ai considerandi della sentenza querelata, ha proposto di respingere il ricorso. Da parte sua la Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni del Cantone Ticino si è rimessa al giudizio di questa Corte.
Diritto:
1. Il Tribunale federale esamina d'ufficio e con piena cognizione la sua competenza (art. 29 cpv. 1 LTF), rispettivamente l'ammissibilità dei gravami che gli vengono sottoposti (DTF 134 IV 36 consid. 1; 133 II 249 consid. 1.1 con riferimenti).
2. 2.1 Il 1° gennaio 2008 è entrata in vigore la legge federale sugli stranieri del 16 dicembre 2005 (LStr; RS 142.20; RU 2007 5487), che ha di per sé abrogato la legge federale concernente la dimora e il domicilio degli stranieri del 26 marzo 1931 (LDDS; CS 1 177 e modifiche seguenti; cfr. Allegato n. I LStr). Giusta l'art. 126 cpv. 1 LStr, alle domande presentate prima dell'entrata in vigore della nuova normativa rimane tuttavia applicabile il diritto previgente. In concreto la decisione di divieto d'entrata è stata promulgata il 21 aprile 2006: dal profilo del diritto interno, l'esame del caso va pertanto svolto in funzione del pregresso ordinamento.
2.2 Le decisioni in materia di divieto d'entrata sono pronunciate dall'Ufficio federale della migrazione (art. 13 cpv. 1 e 15 cpv. 3 LDDS; cfr. art 67 LStr) con facoltà di ricorso al Tribunale amministrativo federale (art. 20 cpv. 1 LDDS; cfr. art. 112 LStr). Giusta l'art. 1 cpv. 2 LTAF, in quanto la legge non escluda il ricorso al Tribunale federale, il Tribunale amministrativo federale giudica quale autorità di grado precedente.
2.3 Giusta l'art. 83 lett. c cifra 1 LTF, il ricorso in materia di diritto pubblico è inammissibile contro le decisioni in materia di diritto degli stranieri concernenti l'entrata in Svizzera. Sennonché come già spiegato dal Tribunale federale (cfr. DTF 131 II 352 consid. 1 così come le sentenze 2C_375/2007 dell'8 novembre 2007 consid. 2.2.2 e 2C_378/2007 del 14 gennaio 2008 consid. 2.1), questo motivo di esclusione non si applica trattandosi dei gravami inoltrati da stranieri che possono, come in concreto, prevalersi 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 (in seguito ALC o Accordo; RS 0.142.112.681): al fine di evitare una violazione del diritto convenzionale, questa Corte entra infatti nel merito dei loro ricorsi basandosi direttamente sull'art. 11 cpv. 3 ALC. Visto quanto precede, la presente impugnativa è quindi, di principio, ammissibile.
2.4 In ragione dell'effetto devolutivo della procedura ricorsuale, l'impugnativa è comunque inammissibile nella misura in cui il ricorrente chiede anche l'annullamento della decisione dell'Ufficio federale della migrazione (DTF 129 II 438 consid. 1).
3. 3.1 Oggetto del contendere è un divieto d'entrata adottato in applicazione dell'art. 13 cpv. 1 prima frase LDDS, secondo cui l'autorità federale può vietare l'entrata in Svizzera di stranieri indesiderabili. Ai cittadini degli Stati membri della Comunità europea e ai loro familiari questa legge si applica tuttavia solo nella misura in cui l'Accordo sulla libera circolazione non disponga altrimenti oppure se essa preveda disposizioni più favorevoli (art. 1 lett. a LDDS). Ne deriva che il provvedimento in esame, limitativo di una prerogativa stabilita dall'Accordo (art. 1 e 3 ALC nonché art. 1 Allegato I ALC) può essere fondato solo su motivi di ordine pubblico, pubblica sicurezza e pubblica sanità (sulla nozione di ordine pubblico, cfr. DTF 130 II 176; 129 II 215 consid. 6.2 e riferimenti; causa CGCE del 27 ottobre 1997 Boucherau C-30/77, Racc. 1977 pag. 1999 n. 33-35)). Tali nozioni vanno intese nel senso definito dalla direttiva 64/221/CEE, del 25 febbraio 1964, e dalla relativa giurisprudenza della CGCE precedente alla sottoscrizione dell'ALC (art. 5 cpv. 2 Allegato I ALC combinato con l'art. 16 cpv. 2 ALC; DTF 131 II 352 consid. 3.1 e riferimenti).
3.2 Conformemente alla giurisprudenza della CGCE (sentenze del 27 ottobre 1977 nella causa 30-77, Bouchereau, Racc. 1977, 1999, n. 33-35, e del 19 gennaio 1999 nella causa C-348/96, Calfa, Racc. 1999, I-11, n. 23 e 25), le deroghe alla libera circolazione devono essere interpretate restrittivamente. L'adozione di misure d'allontanamento presuppone quindi, al di là della turbativa insita in ogni violazione di legge, una minaccia effettiva e sufficientemente grave che tocca un interesse fondamentale della società (cfr. DTF 130 II 176 consid. 3.4.1; 129 II 215 consid. 7.3). La sola esistenza di condanne penali non può automaticamente legittimare l'adozione di provvedimenti fondati su motivi di ordine pubblico o di pubblica sicurezza (cfr. l'art. 3 cpv. 2 della Direttiva 64/221/CEE). Una condanna può piuttosto venir presa in considerazione soltanto nella misura in cui dalle circostanze che l'hanno determinata emerga un comportamento personale costituente una minaccia attuale per l'ordine pubblico. A seconda dei casi, già la sola condotta tenuta in passato può comunque adempiere i requisiti di una simile messa in pericolo dell'ordine pubblico (DTF 130 II 493 consid. 3.2, 176 consid. 3.4.1; 129 II 215 consid. 7.3 e 7.4 e le sentenze della CGCE citate in precedenza). Per valutare l'attualità della minaccia, non occorre prevedere quasi con certezza che lo straniero commetterà altre infrazioni in futuro; d'altro lato, per rinunciare a misure di ordine pubblico, non si deve esigere che il rischio di recidiva sia praticamente nullo. La misura dell'apprezzamento dipende in sostanza dalla gravità della potenziale infrazione: tanto più questa appare importante, quanto minori sono le esigenze in merito al rischio di recidiva (DTF 130 II 493 consid. 3.3, 176 consid. 4.3.1 con rinvii). Inoltre, come nel caso di qualsiasi altro cittadino straniero, l'esame dev'essere effettuato tenendo presente le garanzie derivanti della CEDU (RS 0.101) così come il principio della proporzionalità (DTF 131 II 352 consid. 3.3 e numerosi richiami; sentenze CGCE del 28 ottobre 1975 nella causa 36-75, Rutili, Racc. 1975, 1219, n. 32 e dell'11 luglio 2002, nella causa C-60/00, Carpenter, Racc. 2002, I-6279, n. 42 segg.).
4. 4.1 Come accennato in narrativa, il ricorrente è stato condannato il 17 marzo 2006 dal Presidente della Corte delle assise correzionali di Mendrisio alla pena di due anni di detenzione e all'espulsione dalla Svizzera per un periodo di sette anni, per complicità in rapina aggravata, complicità in rapina e atti preparatori punibili di rapina. Per quanto concerne la pena accessoria dell'espulsione dalla Svizzera, la stessa è decaduta il 1° gennaio 2007, in seguito all'entrata in vigore, a tale data, della legge federale del 13 dicembre 2002 che modifica la parte generale del Codice penale (RU 2006 3459; cfr. art. 388 cpv. 2 CP nonché disposizioni finali della modifica del 13 dicembre 2002, n. 1 cpv. 2). Il ricorrente è stato ritenuto colpevole di complicità in rapina aggravata e complicità in rapina per aver l'8 settembre 2003, e in epoca precedente, intenzionalmente aiutato un terzo nella commissione di una rapina ai danni di un'impiegata di banca e per avere, il 22 ottobre 2003 e in epoca precedente, intenzionalmente aiutato due altre persone nella commissione di una rapina ai danni del gerente di un bar, reato aggravato siccome commesso con arma da fuoco e altra arma pericolosa, in banda e denotando particolare pericolosità e, infine, di atti preparatori punibili di rapina per avere in diverse località ticinesi, nel periodo da febbraio a luglio 2005, in correità con terzi ed agendo conformemente ad un piano, preso concrete disposizioni tecniche ed organizzative finalizzate alla perpetrazione di una rapina ai danni di una gioielleria. I giudici penali hanno poi precisato che anche se le imputazioni erano derubricate da correo a complice, nondimeno le stesse rimanevano comunque molto gravi, considerato pure che era recidivo, con vari precedenti penali alle spalle, e che era ricaduto in un reato analogo a quello per cui era già stato condannato in Italia nel 1983 a 6 anni di reclusione.
4.2 Il ricorrente rimprovera all'autorità inferiore di avere dato rilievo nel proprio giudizio alla circostanza che egli avrebbe minacciato con una pistola il gerente di un esercizio pubblico nel corso di una rapina. Orbene, tale episodio non si è mai verificato in quanto, come emerge dai documenti prodotti (cfr. scritti del 9 febbraio 2006 del Procuratore pubblico e del 10 febbraio 2006 del Tribunale penale cantonale), il Procuratore pubblico nel redigere l'atto di accusa ha confuso due nomi, errore ripreso poi nella sentenza penale. Oltre al fatto che trattasi di un errore palese, siccome eccettuato il passaggio incriminato egli non è mai designato come protagonista, un simile comportamento gli avrebbe valuto una condanna per correità, non per complicità. L'autorità inferiore, dando per acquisita simile circostanza malgrado le evidenti contraddizioni agli atti e senza averlo prima interpellato al riguardo, si sarebbe pertanto basata su di una constatazione arbitraria dei fatti nonché avrebbe violato il suo diritto di essere sentito. Tutto ciò porterebbe inoltre ad un risultato arbitrario poiché a causa di tale errore la citata autorità non avrebbe tenuto conto del fatto che egli ha assunto solo un ruolo di mero complice, elemento rilevante per pronunciarsi sulla sua pericolosità, così come non avrebbe considerato il comportamento esemplare assunto nell'ambito dell'espiazione della pena detentiva e posteriormente alla liberazione.
4.3 Il Tribunale amministrativo federale si è pronunciato, tra l'altro, sulla sussistenza di un comportamento personale costituente una minaccia attuale per l'ordine pubblico, atto a legittimare un provvedimento per ragioni di ordine pubblico ai sensi dell'art. 5 cpv. 1 Allegato I ALC. A tal fine ha insistito - citando il corrispondente estratto della sentenza penale - sul fatto che il ricorrente aveva, durante la rapina del 22 ottobre 2003, sotto la minaccia di una pistola, puntata contro la nuca e poi contro il fianco sinistro, costretto la vittima a raggiungere l'ufficio, intimandole di non urlare, minacciandola di ucciderla e costringendola ad aprire la cassaforte, dalla quale prelevava tutto il contenuto. Orbene, come rettamente osservato dal ricorrente e comprovato dai documenti prodotti (cfr. lettere del 9 febbraio 2006 del Procuratore pubblico e del 10 febbraio 2006 del Tribunale penale cantonale), si tratta di un atteggiamento che questi non ha avuto e che gli è stato attribuito a torto. In effetti quando ha redatto l'atto di accusa il Procuratore pubblico ha confuso - in un paragrafo - le generalità di due prevenuti, errore poi ripreso nella sentenza penale ove il menzionato documento è ampiamente citato. È chiaro che si tratta di una svista manifesta dato che viene fatta menzione del ricorrente in un unico paragrafo del considerando ove viene descritto lo svolgimento della rapina. Inoltre tale menzione interrompe la logica della descrizione degli eventi, siccome nei precedenti e nei successivi paragrafi sono citati i due prevenuti condannati poi come autori. L'errore poteva per di più essere percepito anche da un'attenta lettura della sentenza penale visto che, se avesse effettivamente avuto l'atteggiamento addebitatogli, il ricorrente sarebbe stato condannato come autore, non quale complice.
Al riguardo occorre poi precisare che sebbene una rapina sia un crimine particolarmente grave, la circostanza che una persona non ne era l'autore ma ha assunto solo un ruolo secondario, agendo quale complice, costituisce un elemento determinante nella valutazione della sua pericolosità: il complice infatti non ha alcuna influenza né potere decisionale, alla differenza dell'autore che con il suo comportamento (in concreto puntando una pistola contro la nuca della vittima e minacciandola) influisce sull'evolvere degli avvenimenti. Attribuendo al ricorrente un ruolo principale molto grave che questi, in realtà, non ha mai avuto e basandosi in gran parte sul medesimo per valutare la sua pericolosità dal profilo dell'Accordo sulla libera circolazione delle persone, l'autorità inferiore - la quale fruisce, a differenza di questa Corte, di un ampio potere di apprezzamento (cfr. art. 49 PA per rinvio dell'art. 37 LTAF) - ha quindi constatato in modo manifestamente inesatto e incompleto fatti giuridicamente rilevanti ai fini del giudizio ed ha, di conseguenza, emanato un giudizio manifestamente inficiato d'arbitrio (al riguardo, cfr. DTF 133 II 249 consid. 1.4.3) nonché lesivo dell'art. 5 cpv. 1 Allegato I ALC. La sentenza querelata deve di conseguenza essere annullata e la causa rinviata al Tribunale amministrativo federale affinché proceda ad un nuovo esame della fattispecie nonché emani in seguito un nuovo giudizio.
In queste condizioni non occorre pronunciarsi ancora sulle altre censure sollevate dal ricorrente.
5. 5.1 Da quel che precede discende che il ricorso dev'essere accolto, la decisione impugnata annullata e la causa rinviata al Tribunale amministrativo federale per nuova valutazione della fattispecie e nuovo giudizio (art. 107 cpv. 2 LTF).
5.2 Soccombente, la Confederazione è comunque dispensata dal pagamento delle spese giudiziarie, in quanto non sono in gioco i suoi interessi pecuniari (art. 66 cpv. 4 LTF). Essa dovrà tuttavia versare al ricorrente, assistito da un avvocato, un'indennità per ripetibili della sede federale (art. 68 LTF).
Per questi motivi, il Tribunale federale pronuncia:
1. In quanto ammissibile il ricorso è accolto e la sentenza impugnata è annullata. La causa viene rinviata al Tribunale amministrativo federale, III Corte, per nuovo giudizio ai sensi dei considerandi.
2. Non si prelevano spese giudiziarie.
3. La Confederazione rifonderà al ricorrente un'indennità di fr. 2'000.-- a titolo di ripetibili per la procedura dinanzi al Tribunale federale.
4. Comunicazione al patrocinatore del ricorrente, all'Ufficio federale della migrazione e al Tribunale amministrativo federale, Corte III nonché alla Sezione dei permessi e dell'immigrazione del Dipartimento delle istituzioni del Cantone Ticino (per informazione).