Fatti:
A. Lo Stato del Cantone Ticino ha chiesto all'Ufficio di esecuzione e fallimenti di Locarno di spiccare un precetto esecutivo in via di realizzazione del pegno nei confronti di B._ per l'incasso di fr. 729,10, oltre interessi e spese, per le imposte cantonali 1991/92. Nella domanda di esecuzione il creditore aveva indicato che il debitore era di ignota dimora. Il 26 ottobre 2007 l'Ufficio ha pubblicato sul Foglio ufficiale del Cantone Ticino e sul Foglio ufficiale svizzero di commercio il precetto esecutivo n. 737'161. Anche i successivi atti esecutivi sono stati notificati in via edittale e al pubblico incanto del 5 marzo 2009 la particella n. 669 RFP di X._, di proprietà dell'escusso, è stata aggiudicata ad A._ per fr. 3'500.--.
B. Il 4 e il 18 maggio 2009 B._ ha presentato alla Divisione delle contribuzioni del Cantone Ticino una richiesta di risarcimento di fr. 210'000.-- per aver causato la vendita del suo fondo, senza avergli comunicato l'esistenza di un'esecuzione. L'escusso ha affermato che gli atti esecutivi avrebbero dovuto essergli notificati al suo domicilio di Berna, atteso che il suo indirizzo era facilmente accertabile e noto al creditore procedente perché utilizzato in pratiche fiscali più recenti.
C. Il 6 ottobre 2009 lo Stato del Cantone Ticino ha chiesto alla Camera di esecuzione e fallimenti del Tribunale di appello del Cantone Ticino, quale autorità di vigilanza sugli uffici di esecuzione, di accertare la nullità dell'aggiudicazione, perché fondata su un precetto esecutivo che è stato irritualmente notificato in via edittale invece che al domicilio dell'escusso. Con osservazioni 16 ottobre 2009 l'escusso ha aderito all'istanza, mentre l'aggiudicatario non ha presentato osservazioni.
Con decisione 23 novembre 2009 l'autorità di vigilanza ha accolto l'istanza e ha pronunciato la nullità dell'esecuzione e segnatamente dell'aggiudicazione del predetto fondo. Essa ha altresì ordinato all'Ufficio di far annullare l'iscrizione a registro fondiario, di restituire all'aggiudicatario il prezzo pagato e di chiedere al creditore procedente la restituzione dell'importo percepito e il pagamento delle spese dell'intera procedura. L'autorità di vigilanza ha considerato che in concreto l'irregolarità della notifica edittale era a giusta ragione pacifica e ha accertato che l'escusso non è venuto a conoscenza della procedura esecutiva prima dell'asta. Essa ha poi indicato che la nullità giusta l'<ref-law> di atti esecutivi va rilevata d'ufficio e ha reputato che tutti gli atti esecutivi eseguiti prima che l'escusso venga a conoscenza dell'irregolare notifica di un precetto esecutivo sarebbero nulli. Per questo motivo ha ritenuto nulla l'intera procedura di esecuzione, inclusa l'aggiudicazione, indipendentemente dal fatto che né l'escusso né il creditore procedente l'abbiano impugnata tempestivamente.
D. Con ricorso in materia civile del 10 dicembre 2009 A._ chiede l'annullamento della decisione dell'autorità di vigilanza. Narrati e completati i fatti, asserisce che l'istanza di nullità sarebbe tardiva, poiché intervenuta mesi dopo che le parti hanno avuto conoscenza della vendita all'asta del fondo e che gli eventuali errori commessi nella procedura esecutiva sarebbero imputabili al creditore procedente, che ha fornito indicazioni errate sul domicilio del debitore, e a quest'ultimo, che non ha ricorso. Afferma inoltre che un'ingiustificata notifica edittale sarebbe unicamente annullabile e non nulla e ritiene inammissibile e contrario alla sicurezza del diritto che l'autorità di vigilanza possa dichiarare nulla l'esecuzione. Assevera pure di aver avuto notevoli spese per il ripristino dello stabile, di essere in buona fede e che la decisione impugnata viola l'<ref-law>. Termina il rimedio contestando la competenza dell'autorità di vigilanza di ordinare all'Ufficio di esecuzione di provvedere a far annullare il trapasso di proprietà, perché ciò sarebbe di competenza del giudice civile adito con un'azione di reiscrizione e lamenta una violazione del suo diritto di essere sentito, perché l'istanza del creditore, sulla quale era stato invitato a pronunciarsi, non menzionava la restituzione dell'immobile.
Con decreto del 29 marzo 2010 la Presidente della II Corte di diritto civile ha conferito effetto sospensivo al ricorso.
Con risposta 1° luglio 2010 B._ afferma - in estrema sintesi - che gli errori commessi dall'Ufficio sono talmente gravi da giustificare la nullità della procedura esecutiva e propone la reiezione del ricorso. Con osservazioni 5 luglio 2010 l'Ufficio asserisce invece che lo Stato del Cantone Ticino non era legittimato ad impugnare l'aggiudicazione e che il suo intervento era in ogni caso tardivo. Con risposta 14 luglio 2010 lo Stato del Cantone Ticino propone la reiezione del ricorso, asseverando di aver presentato all'autorità di vigilanza un'istanza fondata sulla nullità dell'aggiudicazione cagionata dai vizi di notifica del precetto esecutivo.
Il 28 luglio 2010 il ricorrente ha presentato una replica.
Il 2 settembre 2010 ha avuto luogo una deliberazione orale secondo l'<ref-law>.

Diritto:
1. 1.1 La decisione impugnata, con cui l'autorità di vigilanza ha dichiarato nulla l'esecuzione su segnalazione del creditore procedente, è finale (<ref-law>) e suscettiva di un ricorso in materia civile ai sensi dell'<ref-law>, indipendentemente dal valore di lite (art. 74 cpv. 2 lett. c LTF). Il ricorso, consegnato alla posta svizzera entro il termine di 10 giorni dalla notificazione del testo integrale della decisione impugnata (art. 48 cpv. 1 e 100 cpv. 2 lett. a LTF) è pertanto in linea di principio ammissibile.
1.2 In concreto è contestata la decisione con cui l'autorità di vigilanza ha constatato la nullità di un'esecuzione dopo aver ricevuto un'istanza in questo senso. In queste circostanze le argomentazioni ricorsuali concernenti la procedura di risarcimento danni intentata dal debitore nei confronti dell'autorità fiscale si appalesano inconferenti. Inammissibile, perché nuova (<ref-law>), si rivela pure la richiesta di richiamo dell'incarto fiscale.
2. Giusta l'<ref-law> il Tribunale federale fonda la sua sentenza sui fatti accertati dall'autorità inferiore. L'accertamento dei fatti può essere censurato unicamente se è stato svolto in violazione del diritto ai sensi dell'<ref-law> oppure in maniera manifestamente inesatta (<ref-law>); quest'ultima definizione corrisponde a quella di arbitrio (<ref-ruling> consid. 1.2.2 pag. 252) e configura a sua volta una violazione del diritto (<ref-law>; <ref-ruling> consid. 1.4.1 pag. 39). Poiché il divieto d'arbitrio rientra fra i diritti fondamentali, la censura relativa ad una sua violazione va espressamente sollevata e motivata in termini qualificati (<ref-law>; <ref-ruling> consid. 1.2, con rinvii; <ref-ruling> consid. 2.2). Il ricorrente che lamenta una violazione del divieto d'arbitrio non può limitarsi a criticare la decisione impugnata come in una procedura d'appello, dove l'autorità di ricorso gode di cognizione libera, opponendo semplicemente la propria opinione a quella dell'autorità cantonale (<ref-ruling> consid. 4.1 pag. 589; <ref-ruling> consid. 1.3 pag. 262), bensì deve dimostrare, attraverso un'argomentazione precisa, che la decisione impugnata si fonda su un'applicazione della legge od un apprezzamento delle prove manifestamente insostenibile (<ref-ruling> consid. 3; <ref-ruling> consid. 2 pag. 639; <ref-ruling> consid. 1.4).
3. Il ricorrente lamenta genericamente una violazione dell'<ref-law>, perché l'autorità di vigilanza non avrebbe accertato i fatti rilevanti, e sostiene in particolare che essa avrebbe omesso di constatare quando il debitore sia effettivamente venuto a conoscenza "della questione".
Giova innanzi tutto rilevare che nella sede cantonale il ricorrente non ha dato seguito all'invito di formulare osservazioni all'istanza del creditore. Ora, l'<ref-law> non esonera coloro che hanno partecipato ad una procedura di esecuzione forzata dall'obbligo di collaborare ed esprimersi innanzi all'autorità di vigilanza sulle circostanze ritenute rilevanti; se essi non si pronunciano, non spetta all'autorità di vigilanza di indagare su fatti che non risultano dagli atti (<ref-ruling> consid. 3). Contrariamente a quanto ritenuto dal ricorrente, dalla sentenza impugnata risulta che l'autorità di vigilanza ha constatato che il debitore non ha avuto conoscenza della procedura esecutiva prima dell'asta. Le speculazioni contenute nel gravame sulla possibilità che l'escusso sia invece venuto a conoscenza dell'esecuzione in un momento anteriore non soddisfano le esigenze di motivazione poste ad un'ammissibile critica degli accertamenti di fatto operati dall'autorità inferiore (supra, consid. 2). Non è infine comprensibile la rilevanza ai fini del presente giudizio del fatto, sollevato dal ricorrente in relazione all'asserita violazione dell'<ref-law>, che il debitore sarebbe stato indicato dall'autorità fiscale con il suo primo prenome, il suo avvocato lo avrebbe invece menzionato con il suo secondo prenome, mentre l'autorità di vigilanza ha indicato entrambi. Ne segue che per la presente sentenza il Tribunale federale si fonda sulla fattispecie accertata dall'autorità di vigilanza cantonale, e quindi sulla circostanza che l'escusso ha avuto conoscenza effettiva della procedura esecutiva ad incanto avvenuto.
4. Giusta l'<ref-law> l'autorità di vigilanza constata d'ufficio la nullità anche quando la decisione non sia stata impugnata. La nullità dev'essere constatata in ogni tempo (<ref-ruling> consid. 2). Ne segue che se, come ritenuto dall'autorità inferiore, l'esecuzione risulta nulla, è - in linea di principio - del tutto irrilevante che essa sia stata segnalata alcuni mesi dopo l'aggiudicazione e le argomentazioni ricorsuali attinenti alla tardività dell'agire del creditore o alla passività del debitore risulterebbero senza pertinenza. Occorre quindi esaminare se l'esecuzione si appalesa nulla - e non esplica quindi alcun effetto (<ref-ruling> consid. 2.3) - o se essa non è inficiata di tale vizio e l'aggiudicazione avrebbe unicamente potuto essere annullata se contestata con un ricorso ai sensi dell'<ref-law>, come preteso dal ricorrente.
5. Giusta l'<ref-law> la notificazione di un precetto esecutivo si fa mediante pubblicazione quando il domicilio del debitore è sconosciuto. La notificazione edittale del precetto esecutivo costituisce la soluzione estrema; non vi si può far capo prima che il creditore e l'ufficio delle esecuzioni abbiano effettuato tutte le ricerche adeguate alla situazione di fatto per reperire un indirizzo ove possa essere eseguita la notificazione al debitore (<ref-ruling>).
5.1 L'autorità di vigilanza ha considerato che l'Ufficio di esecuzione non ha contestato che la notifica del precetto esecutivo mediante pubblicazione fosse stata irregolare e non ha preteso di aver compiuto indagini sul domicilio del debitore o di aver chiesto al creditore procedente di effettuarne. Essa ha ritenuto che trovare l'indirizzo dell'escusso sarebbe stato facile, atteso che egli compare nell'elenco telefonico e che il creditore gli ha notificato, ad un precedente indirizzo nella medesima città in cui risiede ora, ulteriori tassazioni.
5.2 Contro tali accertamenti il ricorrente non formula alcuna censura conforme alle predette esigenze di motivazione (supra consid. 2). Ne segue che l'autorità di vigilanza ha a giusta ragione ritenuto che in concreto l'<ref-law> non permetteva una notifica edittale. Giova tuttavia precisare che nella fattispecie la notifica in quanto tale non è avvenuta in modo irregolare, come ad esempio accade quando il precetto esecutivo viene lasciato nella buca delle lettere dell'escusso (<ref-ruling>), atteso che non risulta né viene preteso che la pubblicazione, se fossero state realizzate le condizioni per ordinarla, sia stata inficiata da vizi.
6. 6.1 Un precetto esecutivo che viene notificato in via edittale senza che siano dati presupposti per procedere in tal modo non può essere considerato nullo, ma dev'essere impugnato entro il termine previsto dall'<ref-law>, che inizia a decorrere dalla conoscenza della notifica edittale. Se, come accade di regola, la procedura continua prima che tale termine sia scaduto o abbia addirittura iniziato a decorrere, il debitore può attaccare anche gli atti successivi facendo valere che la notifica edittale del precetto esecutivo era avvenuta a torto ed impedire così che tali atti crescano in giudicato (DTF 75 III 81 consid. 2; <ref-ruling> consid. 2). A giusta ragione, quindi, il ricorrente sostiene che una notifica edittale del precetto esecutivo avvenuta in dispregio dell'<ref-law> è unicamente annullabile. La fattispecie in esame non si caratterizza tuttavia in primo luogo per la discussa notifica del precetto esecutivo, ma si contraddistingue per la circostanza che tutta la procedura si è svolta ad insaputa del debitore, nonostante il fatto che il suo recapito fosse facilmente reperibile.
6.2 Secondo la giurisprudenza decisioni viziate sono nulle, se il vizio che le inficia è particolarmente grave, se è manifesto o almeno facilmente riconoscibile e se la sicurezza del diritto non viene seriamente messa in pericolo (<ref-ruling> consid. 2.1, con rinvii). Il Tribunale federale ha già avuto modo di specificare che una sentenza contumaciale emanata in seguito ad un'inammissibile convocazione edittale e senza che il convenuto fosse a conoscenza del processo e abbia potuto parteciparvi è toccata da un vizio procedurale talmente grave da risultare nulla (<ref-ruling> consid. 2.2; v. anche <ref-ruling> consid. 3).
6.3 Come già osservato, in concreto tutta la procedura di esecuzione si è svolta - con riferimento alle comunicazioni da trasmettere all'escusso - in via edittale, senza che fossero dati i presupposti per procedere in tal modo ed impedendo così al debitore di tutelare i suoi diritti. Quest'ultimo è inoltre venuto a conoscenza della procedura esecutiva unicamente ad incanto avvenuto (supra, consid. 3 cpv. 2). Nella fattispecie in esame l'escusso è quindi stato - senza motivo - escluso dalla procedura che ha portato all'alienazione del suo fondo in modo analogo a quanto accaduto nel processo contumaciale di cui alla <ref-ruling>. In queste circostanze, la procedura esecutiva risulta essere inficiata da un vizio talmente grave da dover essere considerata nulla.
6.4 Il ricorrente ritiene che la sicurezza del diritto, la sua buona fede e le spese già sopportate per il fondo in discussione siano di ostacolo alla reiezione del rimedio. Giova innanzi tutto rilevare che l'argomentazione è, per quanto concerne i pretesi investimenti sostenuti per il ripristino del fondo, inammissibilmente (supra consid. 2 e 3 cpv. 2) fondata su circostanze non accertate dall'autorità di vigilanza e nemmeno fatte valere nella sede cantonale. Per il resto si può osservare che la contestazione dell'aggiudicazione è stata segnalata al ricorrente prima che fosse trascorso un anno dall'incanto (DTF <ref-ruling> consid. 1 pag. 60), periodo durante il quale l'aggiudicatario - indipendentemente dalla sua buona fede - deve aspettarsi una possibile impugnazione (<ref-law>) e la conseguente revoca dell'aggiudicazione.
7. Del tutto infondate si rivelano infine le argomentazioni con cui il ricorrente lamenta che l'autorità di vigilanza non avrebbe potuto ordinare all'Ufficio di esecuzione "di intervenire" presso l'Ufficio del registro fon-diario per far annullare l'iscrizione del trapasso di proprietà. Rientra manifestamente nelle competenze dell'autorità di vigilanza impartire istruzioni agli Uffici che le sono subordinati. Altrettanto inconsistente si rivela la pretesa violazione del diritto di essere sentito del ricorrente. Infatti, nemmeno quest'ultimo afferma di non essersi potuto esprimere sull'istanza del creditore che segnalava esplicitamente all'autorità di vigilanza la nullità dell'aggiudicazione. Ora, fra le evidenti conseguenze della fondatezza di una tale segnalazione si annoverano la revoca dell'aggiudicazione e la richiesta all'Ufficio del registro fondiario di cancellare il trapasso di proprietà (JAEGER/WALDER/KULL, Bundesgesetz über Schuldbetreibung und Konkurs, 5a ed. 2006, n. 9 ad <ref-law>).
8. Da quanto precede discende che il ricorso si rivela, nella misura in cui è ammissibile, infondato e come tale va respinto. Le spese giudiziarie e le ripetibili seguono la soccombenza (art. 66 cpv. 1 e 68 cpv. 1 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 3'000.-- sono poste a carico del ricorrente, che rifonderà all'opponente B._ fr. 3'000.-- per ripetibili della sede federale.
3. Comunicazione alle parti e alla Camera di esecuzione e fallimenti del Tribunale d'appello del Cantone Ticino, quale autorità di vigilanza.