Fatti:
A. Con decisione del 16 maggio 2008 la Cassa di compensazione AVS/AI/IPG del Cantone Ticino ha chiesto al Comune X._ la restituzione delle indennità versate a torto negli anni 2004 e 2005 (per un totale di fr. 4'392.35) per i giorni di servizio effettuati dal seguente suo milite - al tempo stesso dipendente dell'organizzazione - ed erroneamente conteggiati a carico dell'ordinamento sulle indennità di perdita di guadagno per chi presta servizio e in caso di maternità (LIPG):
- A._ (30 giorni di servizio [2004: 17; 2005: 13] chiesti in restituzione a fronte di 58 giorni attestati e indennizzati).
Con decisione su opposizione del 7 aprile 2009 la Cassa cantonale di compensazione ha confermato il contenuto del provvedimento.
B. Per pronuncia del 5 maggio 2010 il Tribunale delle assicurazioni del Cantone Ticino ha accolto il ricorso del Comune X._ e ha annullato la decisione amministrativa, dichiarando perenta la richiesta di restituzione.
C. La Cassa cantonale di compensazione ha presentato ricorso in materia di diritto pubblico al Tribunale federale al quale chiede, in via principale, l'annullamento della pronuncia cantonale e la conferma della decisione amministrativa e, in via subordinata, l'annullamento di detto giudizio nonché il rinvio della causa all'istanza precedente per complemento istruttorio.
Il Comune X._ ha proposto la reiezione del gravame, mentre l'Ufficio federale delle assicurazioni sociali (UFAS) ne ha chiesto l'accoglimento.

Diritto:
1. Le osservazioni dell'UFAS sono state presentate il 15 settembre 2010, vale a dire ampiamente dopo la scadenza del termine fissato - al 5 agosto 2010 - da questa Corte con decreto del 22 luglio 2010. Poiché il ritardo, apparentemente dovuto a un errore di registrazione, non è scusabile ai sensi dell'<ref-law>, l'avviso non può essere preso in considerazione (in relazione al precedente ordinamento di organizzazione giudiziaria federale cfr. consid. 1 non pubblicato in <ref-ruling>, ma in RCC 1989 pag. 471; <ref-ruling> consid. 1 pag. 197; inoltre sentenza del Tribunale federale delle assicurazioni B 24/05 del 15 marzo 2006 consid. 1).
2. Il ricorso in materia di diritto pubblico può essere presentato per violazione del diritto, così come stabilito dagli art. 95 e 96 LTF. Per contro, il Tribunale federale fonda la sua sentenza sui fatti accertati dall'autorità inferiore (<ref-law>) e vi si può scostare solo qualora questo accertamento sia avvenuto in modo manifestamente inesatto, ovvero arbitrario (<ref-ruling> consid. 4.3 pag. 62), o in violazione del diritto ai sensi dell'<ref-law> (<ref-law>). Salvo i casi in cui tale inesattezza sia lampante (cfr. <ref-ruling> consid. 6.2 pag. 288 in fine), la parte ricorrente che intende contestare i fatti accertati dall'autorità inferiore deve spiegare, in maniera circostanziata, per quale motivo ritiene che le condizioni di una delle eccezioni previste dall'<ref-law> sarebbero realizzate; in caso contrario non si può tener conto di uno stato di fatto diverso da quello posto a fondamento della decisione impugnata (cfr. <ref-ruling> consid. 1.4.3 pag. 254 con riferimento).
3. Oggetto del contendere in sede federale è unicamente il tema di sapere se la richiesta di restituzione formulata dalla Cassa ricorrente fosse effettivamente tardiva, come ha ritenuto l'autorità giudiziaria cantonale.
3.1 Giusta l'<ref-law>, le prestazioni indebitamente riscosse devono essere restituite. La restituzione non deve essere chiesta se l'interessato era in buona fede e verrebbe a trovarsi in gravi difficoltà (cpv. 1). Il diritto di esigere la restituzione si estingue dopo un anno a decorrere dal momento in cui l'istituto d'assicurazione ha avuto conoscenza del fatto, ma al più tardi cinque anni dopo il versamento della prestazione. Se il credito deriva da un atto punibile per il quale il diritto penale prevede un termine di prescrizione più lungo, quest'ultimo è determinante (cpv. 2).
3.2 Il termine annuo di perenzione comincia normalmente a decorrere nel momento in cui l'amministrazione, usando l'attenzione da essa ragionevolmente esigibile avuto riguardo alle circostanze, avrebbe dovuto rendersi conto dei fatti giustificanti la restituzione (<ref-ruling> consid. 3a pag. 433; <ref-ruling>). Ciò si verifica quando l'amministrazione dispone di tutti gli elementi decisivi nel caso concreto dalla cui conoscenza risulti di principio e nel suo ammontare l'obbligo di restituzione di una determinata persona (<ref-ruling> consid. 3 pag. 17). Se l'istituto assicuratore dispone di sufficienti indizi circa una possibile pretesa di restituzione, ma la documentazione si rivela ancora incompleta, esso è tenuto ad esperire i necessari accertamenti entro un termine adeguato. In caso di ritardo, l'inizio del termine di perenzione viene fatto risalire al momento in cui l'amministrazione, con l'impegno ragionevolmente esigibile, sarebbe stata in grado di acquisire la necessaria conoscenza in modo tale da potere esercitare il diritto alla restituzione. Il termine annuo di perenzione comincia in ogni caso a decorrere non appena dagli atti emerge direttamente l'irregolarità della corresponsione delle prestazioni (consid. 5.1 non pubblicato in <ref-ruling>, ma in SVR 2008 KV n. 4 pag. 11 [K 70/06]; cfr. pure sentenza 9C_1057/2008 del 4 maggio 2009 consid. 4.1.1).
3.3 Se per l'accertamento e l'esame del diritto alla restituzione è necessaria la collaborazione tra più unità amministrative incaricate dell'attuazione dell'assicurazione, la conoscenza anche di una sola di esse è sufficiente a fare decorrere i termini (<ref-ruling> consid. 4c pag. 182 seg.; RCC 1989 pag. 558). Ora, l'attuazione dell'ordinamento in materia di indennità di perdita di guadagno compete agli organi dell'assicurazione vecchiaia e superstiti, per la protezione civile con la collaborazione dei contabili degli organi di protezione (<ref-law>). Nel Cantone Ticino, la vigilanza generale sull'esecuzione delle prescrizioni federali e cantonali in materia di protezione civile è assunta dal Consiglio di Stato (art. 2 della legge cantonale di applicazione alla legge federale del 23 marzo 1962 sulla protezione civile del 7 novembre 1988 [Bollettino ufficiale delle leggi e degli atti esecutivi (BU) n. 55/1988 del 16 dicembre 1988 pag. 355 segg.], in vigore fino al 30 giugno 2008 e dunque applicabile al caso di specie). Questa competenza è stata (sub)delegata al Dipartimento cantonale delle Istituzioni e da questi all'Ufficio di protezione civile (art. 3 legge cantonale di applicazione e art. 1 del regolamento cantonale sulla protezione civile del 1° febbraio 1994 [BU n. 5/1994 dell'8 febbraio 1994 pag. 55]), cui compete il compito di emanare le direttive atte a promuovere la corretta applicazione delle disposizioni federali e cantonali nel limite delle competenze attribuite ai Cantoni e, come autorità di vigilanza, anche il compito di controllare che tutte le prescrizioni federali e cantonali in materia di protezione civile siano correttamente interpretate e applicate. Tale organizzazione è stata ripresa dalla nuova legge cantonale sulla protezione civile del 26 febbraio 2007, in vigore dal 1° luglio 2008 [RL/TI 1.5.4.1], e dal relativo regolamento di applicazione del 3 giugno 2008 (cfr. il suo art. 1 [RL/TI 1.5.4.1.1]). La Confederazione esercita la vigilanza sull'ordinamento sulle indennità di perdita di guadagno. Competente è il Consiglio federale, il quale può incaricare l'UFAS di impartire istruzioni agli enti incaricati dell'attuazione dell'assicurazione allo scopo di garantire un'applicazione unitaria (<ref-law> in relazione con gli <ref-law> e 72 cpv. 1 LAVS).
3.4 Chi presta servizio di protezione civile ha diritto ad un'indennità per perdita di guadagno secondo le disposizioni della LIPG (art. 23 della legge federale sulla protezione della popolazione e sulla protezione civile [LPPC; RS 520.1] del 4 ottobre 2002, in vigore dal 1° gennaio 2004, come pure della - nel frattempo, a fine 2003 - abrogata legge federale del 17 giugno 1994 sulla protezione civile [LPCi; RU 1994 2626 segg.]). Con riferimento ai giorni di servizio conteggiabili a carico della LIPG valeva e vale, per quanto qui di interesse, la seguente regolamentazione. Sino a fine 2003 potevano essere indennizzati al massimo 40 giorni per anno civile e per milite. Nessuna restrizione era prevista per gli interventi in caso di catastrofe e altre situazioni d'emergenza (art. 12, 23 e 37 cpv. 3 LPCi). Dal 1° gennaio 2004 i militi con funzioni di quadro e di specialista possono essere chiamati a prestare corsi di ripetizione di al massimo 14 giorni - limitati a sette per gli altri militi - e a seguire corsi di perfezionamento della durata massima complessiva di due settimane su un periodo di quattro anni (art. 35 e 36 LPPC). La durata degli interventi in caso di catastrofe e altre situazioni d'emergenza come pure di pubblica utilità non è di principio soggetta a limitazione; gli interventi devono però essere specialmente autorizzati dal Consiglio federale o dai Cantoni (art. 23, 27 e 35 segg. LPPC come pure ordinanza federale del 5 dicembre 2003 sugli interventi di pubblica utilità della protezione civile [OIPU; RS 520.14], nella sua versione in vigore fino al 30 giugno 2008 [RU 2003 5175]). I Cantoni disciplinano così la procedura di chiamata (<ref-law>) come pure l'autorizzazione di interventi di pubblica utilità a livello cantonale e comunale e stabiliscono la ripartizione dei costi tra Cantone, Comuni e richiedente (art. 7 OIPU in relazione con l'<ref-law>). L'Ufficio federale della protezione della popolazione (UFPP) controlla l'esecuzione da parte dei Cantoni e Comuni (<ref-law> in relazione con l'art. 41 cpv. 3 ordinanza federale sulla protezione civile [OPCi; RS 520.11] del 5 dicembre 2003).
4. 4.1 Il Tribunale cantonale delle assicurazioni ha accertato che dalle liste elaborate - su richiesta dell'UFAS - dall'UFPP sulla base dei questionari IPG per gli anni 2004/2005 e trasmesse per verifica all'Ufficio cantonale responsabile della protezione civile il 2 febbraio 2007 si evinceva che - rispetto al totale - gran parte dei giorni di servizio poi parzialmente oggetto di restituzione dovevano necessariamente essere - una volta dedotta la durata annua massima indennizzabile per corsi di ripetizione di 14 giorni (<ref-law>) - degli interventi ai sensi dell'<ref-law>, segnatamente a favore della collettività. Richiamandosi a principi giurisprudenziali recentemente sviluppati in materia dal Tribunale federale (sentenze 9C_1057/2008, citata, e 9C_534/2009 del 4 febbraio 2010), i primi giudici ne hanno dedotto che l'entità del numero di giorni di intervento a questo titolo (in casu: 30 sui 58 giorni complessivi attestati e indennizzati) era tale che la Cassa cantonale di compensazione - prestando l'attenzione ragionevolmente esigibile ed accresciuta in ragione del rischio di abuso insito al sistema - avrebbe dovuto insospettirsi e avviare quanto meno delle indagini tese ad accertare l'eventuale esistenza di una pretesa di restituzione. La Corte cantonale ha quindi concluso che qualora la Cassa avesse reagito con la tempestività comandata dalle circostanze, gli accertamenti necessari a verificare l'esistenza di un obbligo alla restituzione per gli anni 2004 e 2005 sarebbero terminati ben prima del 2 febbraio 2007, data dalla quale è stato fatto decorrere, al più tardi, il termine annuo di perenzione dell'<ref-law>. Ma anche qualora si fosse voluto fare decorrere l'inizio del termine di perenzione da un periodo successivo al 2 febbraio 2007, la Sezione del militare e della protezione della popolazione (SMPP), in qualità di organo esecutivo responsabile della protezione civile, avrebbe dovuto, a mente dei primi giudici, essere in grado di determinare la somma delle IPG (eventualmente) pagate in eccesso entro due mesi dalla richiesta di collaborazione formulatale a inizio febbraio 2007. Termine di due mesi che agli occhi degli stessi giudici appariva adeguato anche perché i dati contenuti nelle liste elaborate dall'UFPP rappresentavano ben più di semplici indizi e poiché dai timbri apposti dal capo del Servizio di protezione civile N._ a conferma dell'esattezza dei dati risultava che il lavoro di verifica compiuto dalla SMPP era già terminato il 20 aprile 2007. In ogni caso, dunque, al momento della decisione del 16 maggio 2008 il diritto alla restituzione sarebbe già stato perento.
4.2 La Cassa ricorrente non condivide questa valutazione. Essa osserva in primo luogo che il compito di determinare correttamente il numero di giorni indennizzabili con le IPG compete al contabile degli uffici della protezione civile attraverso l'attestazione conforme all'<ref-law> del "Questionario per il servizio militare e la protezione civile". Sostiene che, anche volendo, un controllo da parte sua sul numero di giorni svolti e attestati non risulterebbe possibile perché i militi possono cambiare la propria cassa di affiliazione nel corso di un anno e perché, nel contesto dei servizi forniti dalla protezione civile a titolo di interventi di pubblica utilità, per i quali non sono (più) stabiliti limiti massimi, il legislatore federale ha predisposto un'apposita procedura di autorizzazione sottratta al controllo delle casse di compensazione. Le quali, continua l'insorgente, devono potersi attenere alle indicazioni attestate dai contabili della protezione civile conformemente al principio della buona fede. Quanto all'osservazione che in virtù della sola entità del numero dei giorni di servizio attestati dai contabili della protezione civile avrebbe dovuto insospettirsi e quanto meno dare avvio a indagini per accertare l'eventuale esistenza di una pretesa di restituzione, l'amministrazione la ritiene anch'essa, per i motivi già indicati in precedenza, contraria al principio della buona fede. Rileva che per dovere maturare un ragionevole dubbio sulla correttezza dell'operato dei contabili degli uffici della protezione civile occorrono ulteriori indizi, concreti e riferiti a casi particolari, che nella fattispecie non sarebbero però dati.
La ricorrente ricorda inoltre il complesso contesto in cui si inserisce la presente causa, caratterizzato dall'avvio, verso la fine del 2006, di un accertamento a livello nazionale denominato "operazione Argus" che ha visto il controllo, da parte dell'UFAS e dell'UFPP, di oltre 50'000 formulari IPG attestanti più di 130'000 giorni di servizio nella protezione civile con un riscontro, fino al 2006, di circa 32'000 giorni di servizio indebitamente forniti e oltre 5 milioni di franchi indebitamente versati sotto forma di IPG. Con riferimento alle liste trasmesse il 2 febbraio 2007 dall'UFPP alla SMPP, la Cassa osserva che esse costituivano solamente un punto di partenza per procedere con i necessari accertamenti, ritenuto che a quella data non sarebbe stato possibile determinare né il principio né tanto meno la misura della pretesa di restituzione. Rimprovera ai giudici cantonali di non avere tenuto in debito conto la comunicazione 25 maggio 2007 con cui il caposervizio della protezione civile N._, rilevando le difficoltà incontrate, aveva trasmesso all'UFPP il risultato delle sue indagini, né tanto meno lo scritto 28 maggio 2009 con cui l'UFPP aveva confermato all'UFAS di avere concluso i propri accertamenti il 25 settembre 2007. Basandosi sul contenuto di queste dichiarazioni ritiene dunque che con l'emanazione della decisione di restituzione del 16 maggio 2008 il termine di perenzione di un anno sarebbe stato in ogni caso rispettato.
5. 5.1 Preliminarmente, nella misura in cui la ricorrente allega per la prima volta in sede federale questioni di fatto che non sono state accertate dall'istanza precedente (quali ad esempio l'utilizzo dello stesso codice, nel "Questionario per il servizio militare e la protezione civile", per indicare sia i corsi di ripetizione sia gli interventi di pubblica utilità), queste non possono essere prese in considerazione (Bernard Corboz, Commentaire de la LTF, 2009, n. 15 ad art. 99). Nuovi fatti e nuovi mezzi di prova non possono infatti essere addotti, a meno che non ne dia motivo la decisione dell'autorità inferiore (<ref-law>; <ref-ruling> consid. 3.3.1). Incombe al ricorrente - che però non lo ha fatto in concreto - spiegare perché ciò si verifichi (<ref-ruling> consid. 3 pag. 395). A ciò si aggiunge che nella misura in cui si richiama al contenuto di successivi giudizi del Tribunale cantonale in vertenze "identiche", essa si riferisce pure a fatti intervenuti successivamente alla data della decisione in lite, che delimita temporalmente il potere di esame del giudice delle assicurazioni sociali (<ref-ruling> consid. 3.1.1 pag. 220; <ref-ruling> consid. 1b pag. 366).
5.2 Laddove invece contesta l'esistenza di un obbligo, da parte sua, di controllo sull'operato dei contabili della protezione civile e lo ritiene contrario alla legislazione in materia come pure al principio della buona fede, l'insorgente dimentica che le sue mansioni nel presente contesto non si limitano al versamento delle prestazioni, ma comprendono anche l'esame e, datene le condizioni, l'emissione di richieste di restituzione. Ora, se usando l'attenzione da essa ragionevolmente esigibile avuto riguardo alle circostanze la Cassa può riconoscere l'esistenza verosimile di un fatto giustificante una richiesta di restituzione, una sua eventuale passività non può ostare all'inizio del termine annuo di perenzione ai sensi dell'<ref-law> (cfr. sentenza 9C_982/2010 del 16 maggio 2011 consid. 3.4.1 in fine).
5.3 Similmente, la ricorrente dimentica che è stato proprio il Tribunale federale a precisare recentemente, in una analoga vertenza, che l'annuncio, per una determinata persona, di un elevato numero di giorni di servizio può costituire non solo possibilmente, ma addirittura molto verosimilmente un indizio per un conteggio delle IPG non conforme alla legge che impone agli organi esecutivi della LIPG (contabili dell'organizzazione di protezione civile, cassa di compensazione) di quanto meno avviare i necessari accertamenti (sentenza citata 9C_1057/2008 consid. 4.4.2). In quella occasione si era trattato di giudicare la richiesta di restituzione formulata dalla cassa di compensazione del Canton Soletta per le indennità IPG versate di troppo al Comune di assoggettamento di due suoi militi. Essendo stati annunciati all'IPG, rispettivamente, 38 e 98 giorni di servizio in più rispetto al numero massimo annuo indennizzabile (di 28 giorni, tra corsi di ripetizione e corsi di perfezionamento), questi giorni di servizio in più sono stati necessariamente considerati interventi straordinari in caso di catastrofe o altre situazioni d'emergenza oppure interventi di pubblica utilità.
Ebbene, per il Tribunale federale, questi numeri avrebbero dovuto da soli, usando l'attenzione ragionevolmente esigibile avuto riguardo alle circostanze, insospettire sia il contabile dell'organizzazione di protezione civile competente, sia l'ufficio cantonale del militare e della protezione civile, sia infine la cassa cantonale di compensazione, tanto più che dal 1° gennaio 2004 gli interventi di pubblica utilità sono unicamente indennizzabili alle condizioni stabilite dalla OIPU e che soprattutto in questo ambito, con la possibilità che servizi a favore del proprio datore di lavoro vengano irregolarmente conteggiati a carico delle IPG, esiste un concreto rischio di abusi (sentenza citata 9C_1057/2008 consid. 4.4.2; Messaggio concernente la revisione totale della legislazione sulla protezione civile del 17 ottobre 2001, FF 2002 1535 segg., 1562).
Le medesime considerazioni sopra espresse si attagliano alla fattispecie per valutare la richiesta di restituzione degli indennizzi versati a torto al Comune opponente in relazione ai giorni di servizio prestati negli anni 2004 e 2005 dal suo milite nonché dipendente A._. Anzi, a ben vedere, le liste elaborate dall'UFPP sulla base dei dati delle domande IPG - i quali erano quindi necessariamente in possesso anche della Cassa di compensazione - mettono in risalto un numero di giorni di corsi di ripetizione (di molto) superiore al limite massimo annuo indennizzabile di 14 giorni (<ref-law>), sicché l'irregolarità della corresponsione delle prestazioni risultava in realtà (almeno per questo genere di servizio) direttamente dagli atti.
5.4 Per il resto non sono dati (e nemmeno invocati) gli estremi per procedere a una modifica della peraltro recente prassi di questa Corte (sul tema cfr. <ref-ruling> consid. 3 pag. 8: 135 I 79 consid. 3 pag. 82; <ref-ruling> consid. 3.3 pag. 76). Pertanto, la decisione del Tribunale cantonale che in applicazione dei suddetti principi ha concluso che qualora la Cassa avesse reagito con la tempestività comandata dalle circostanze, gli accertamenti necessari a verificare l'esistenza di un obbligo alla restituzione per gli anni 2004 e 2005 sarebbero terminati ben prima del 2 febbraio 2007 e che ha quindi fatto decorrere, al più tardi, da tale data l'inizio del termine annuo di perenzione, non risulta né da un accertamento manifestamente inesatto dei fatti determinanti né da una violazione del diritto federale. Non avendo fatto prova dell'attenzione richiesta dalle circostanze, la Cassa non può prevalersi di una ipotetica protezione della buona fede (cfr. per analogia <ref-law>).
5.5 Senza arbitrio la Corte cantonale poteva inoltre, in via abbondanziale, pure ritenere che il giudizio non sarebbe stato diverso nemmeno se avesse fatto decorrere l'inizio del termine di perenzione da un periodo successivo al 2 febbraio 2007 poiché la SMPP, in qualità di organo esecutivo responsabile della protezione civile, avrebbe dovuto essere in grado, entro due mesi dalla richiesta di collaborazione formulatale dall'UFPP, di determinare la somma delle IPG (eventualmente) pagate in eccesso. Questo apprezzamento così come l'accertamento secondo il quale la SMPP avrebbe concluso il proprio lavoro di verifica il 20 aprile 2007, benché opinabile, è sostenibile poiché trova riscontro nei timbri apposti dal capo servizio protezione civile N._ a conferma dell'esattezza dei dati indicati. Il fatto di essersi fondato ai fini della propria valutazione su questa data anziché su quella del 25 maggio 2007, alla quale la SMPP trasmise all'UFPP il risultato delle proprie indagini, o su quella del 25 settembre 2007, per la quale l'UFPP affermò di avere concluso i propri accertamenti, non rende manifestamente inesatto (sul significato di tale presupposto cfr. <ref-ruling> consid. 4.3 pag. 62) o contrario al diritto l'accertamento dei primi giudici. L'eccezione per cui in una procedura federale - quale era l'operazione Argus - scadenzata dall'UFPP non poteva essere decisivo il parere espresso dalla SMPP è inconsistente non fosse altro perché non tiene conto della giurisprudenza in materia che considera sufficiente, per l'inizio del termine annuo di perenzione, la conoscenza dei fatti essenziali anche da parte di una sola delle unità amministrative incaricate (direttamente o indirettamente: cfr. sentenza citata 9C_534/2009 consid. 3.2.2) dell'attuazione dell'assicurazione.
5.6 Quanto alla preoccupazione che una conferma della decisione della Corte cantonale rischierebbe di ostacolare eccessivamente il successo dell'operazione Argus, vale la pena ricordare alla ricorrente quanto già recentemente stabilito, nello stesso contesto, nella sentenza citata 9C_982/2010 in cui, pur dando atto che l'esame coordinato a più livelli di tutti i possibili casi di restituzione per un determinato periodo risponde certamente a esigenze di praticabilità e appare comprensibile, il Tribunale federale ha evidenziato che tale modalità procedurale non può comunque fare dimenticare che sono le circostanze concrete del caso di specie e in particolare lo stato delle conoscenze dei singoli organi di esecuzione a determinare l'inizio del termine di perenzione (sentenza citata consid. 3.4.1 e 3.4.2).
5.7 Non merita per il resto di essere approfondita oltre la questione di sapere se la Cassa non sarebbe in ogni caso (stata) in grado di svolgere un controllo sui giorni di servizio attestati dai contabili della protezione civile dal momento che i militi potrebbero comunque cambiare la propria cassa di affiliazione nel corso di un anno. Tale considerazione è irrilevante per la risoluzione della presente causa non fosse altro perché la Cassa ricorrente non ha sostenuto né tanto meno comprovato un simile cambiamento con riferimento al milite (nonché dipendente del Comune opponente) oggetto della presente procedura di restituzione.
5.8 Senza arbitrio infine la Corte cantonale poteva (implicitamente) procedere a un apprezzamento anticipato delle prove e prescindere dall'audizione - proposta dalla ricorrente - del responsabile della "operazione Argus" K._, del funzionario dell'UFPP P._ e dei funzionari SMPP O._ e N._, i quali difficilmente avrebbero potuto fornire nuove indicazioni di rilievo che non fossero già desumibili dagli atti (<ref-ruling> consid. 3 pag. 157; <ref-ruling> consid. 4a pag. 211).
5.9 Ne segue che il diritto alla restituzione delle prestazioni doveva effettivamente considerarsi perento al momento in cui la Cassa ricorrente ha emesso la decisione del 16 maggio 2008. Il ricorso si dimostra pertanto infondato e la pronuncia impugnata va confermata.
6. Le spese seguono la soccombenza e sono poste a carico della ricorrente (<ref-law>), la quale rifonderà all'opponente, patrocinato da una legale, un'indennità - ridotta vista la motivazione standard utilizzata dalla medesima patrocinatrice anche in altri casi (in questo senso v. ad esempio sentenza 9C_1040/2009 del 7 dicembre 2010 consid. 3.2 con riferimento) - per ripetibili della sede federale (art. 68 cpv. 1 e 2 LTF; cfr. pure sentenza citata 9C_534/2009 consid. 4).

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso è respinto.
2. Le spese giudiziarie di fr. 500.- sono poste a carico della ricorrente.
3. La ricorrente verserà all'opponente la somma di fr. 800.- a titolo di indennità di parte per la procedura federale.
4. Comunicazione alle parti, al Tribunale delle assicurazioni del Cantone Ticino e all'Ufficio federale delle assicurazioni sociali.