Fatti:
A. Il 22 aprile 2004 A._, all'epoca domiciliato a Zurigo, ha fatto spiccare per il tramite dell'Ufficio Esecuzioni (UE) di Lugano un precetto esecutivo nei confronti di B._ SA per fr. 29'696.50 oltre accessori, indicando quale causa dell'obbligazione "Lavori al mappale 291 Bissone - ripristino difetti/lavori non eseguiti + spese di perizia"; fra le parti era infatti pendente un litigio in relazione ai lavori di costruzione eseguiti dall'impresa ticinese sul fondo di proprietà di A._. L'escussa ha interposto opposizione.
B. B.a Il 12 maggio 2004 B._ SA ha a sua volta avviato un'esecuzione contro A._ per il tramite dell'UE di Zurigo per un importo di fr. 100'000.--, motivandola con un "attentato al credito - Attentat auf Kredit". L'escusso ha interposto opposizione.
Egli ha pure interposto formale ricorso al Bezirksgericht di Zurigo, autorità inferiore di sorveglianza sugli uffici esecuzione, che con decisione 2/11 agosto 2004 ha annullato il precetto esecutivo e incaricato l'UE interessato di emetterne uno nuovo, dopo aver chiesto e ottenuto dalla precettante l'indicazione del corretto titolo del credito.
B.b In data 18 agosto 2004 l'UE di Zurigo ha quindi spiccato un nuovo precetto esecutivo, per lo stesso importo, menzionante quale causale del credito "Kreditschädigung infolge ungerechtfertigter Betreibung und vertragswidrigem Garantieabruf". A._ ha nuovamente interposto opposizione.
B.c Il 18 novembre 2004 A._ ha pure convenuto la ditta ticinese dinanzi al Bezirksgericht di Zurigo, postulando in particolare l'accertamento dell'inesistenza del credito e la condanna della precettante al risarcimento del danno cagionatogli dall'emissione del precetto nonché di fr. 5'000.-- per torto morale.
B._ SA ha avversato la domanda, eccependo preliminarmente l'incompetenza territoriale del tribunale zurighese.
Con pronuncia del 15 agosto 2005 il tribunale adito ha accolto l'eccezione, senza entrare nel merito della lite, e ha assegnato a A._ un termine di venti giorni per indicare l'identità del tribunale territorialmente competente, al quale trasmettere la pratica.
Le tasse, spese e ripetibili della procedura zurighese sono state poste a carico di A._.
B.d La causa è stata quindi trasmessa alla Pretura di Lugano. Invitato a presentare un atto introduttivo di causa conforme al Codice di procedura civile ticinese (CPC/TI), il 1° febbraio 2006 A._ ha inoltrato una petizione, con la quale ha riproposto nei confronti di B._ SA le medesime domande di giudizio formulate davanti al giudice zurighese.
Nel corso del mese di marzo 2006 B._ SA ha ritirato il precetto esecutivo oggetto della causa, con conseguente cancellazione dell'esecuzione. Con risposta del 18 settembre 2006 ha poi proposto la reiezione della petizione, eccependo preliminarmente la prescrizione della pretesa relativa al risarcimento dei danni e del torto morale.
In sede di replica A._ ha rilevato che il ritiro del precetto ha reso priva d'oggetto l'azione di accertamento negativo. Contestata la fondatezza dell'eccezione di prescrizione, egli ha ribadito la domanda di accollare alla controparte l'integralità di tasse e spese giudiziarie da lui sopportate a causa della procedura esecutiva nonché la sua condanna, previo accertamento della temerarietà del suo comportamento, al risarcimento di ogni spesa e danno giusta l'<ref-law>/TI. Nel prosieguo di causa ha quantificato le proprie pretese nel modo seguente: fr. 5'000.-- per torto morale; fr. 27'401.20 a titolo di rifusione dei costi di giustizia e di patrocinio sostenuti in relazione alle due procedure avviate a Zurigo; fr. 12'169.40 quale risarcimento di piene ripetibili ex <ref-law>/TI.
Statuendo il 21 luglio 2008 la Pretora ha dichiarato priva d'oggetto la petizione relativamente all'azione di accertamento negativo e, disattesa l'eccezione di prescrizione, l'ha respinta relativamente all'azione di risarcimento. In particolare, la domanda di A._ tendente alla rifusione degli importi pagati in relazione alle due procedure giudiziarie zurighesi è stata respinta per il motivo che il pregiudizio da lui asserito non riguarda alcuna spesa precedente i citati procedimenti (spese preprocessuali) bensì spese connesse ad essi (spese processuali), sulle quali le autorità zurighesi hanno statuito in maniera definitiva. In queste circostanze, la giudice non ha ritenuto applicabile l'<ref-law>/TI.
C. L'impugnativa interposta dal soccombente, limitata al giudizio sull'importo di fr. 27'401.20 e sulle ripetibili di prima sede, è stata respinta dalla II Camera civile del Tribunale d'appello con sentenza del 21 ottobre 2009.
In breve, l'alta Corte ticinese ha negato a A._ la possibilità di trarre vantaggio dalla <ref-ruling>, richiamata nell'appello, giusta la quale la condotta processuale abusiva di una parte può dar luogo a una pretesa di risarcimento danni fondata sull'<ref-law>, indipendente dalla possibilità di essere risarciti in base al diritto di procedura applicabile. Nella fattispecie ci si trova infatti in presenza di due sentenze che "hanno statuito sull'attribuzione di tasse, spese e ripetibili con forza di cosa giudicata, in un caso nell'ambito di una procedura gratuita che non prevedeva il riconoscimento di ripetibili, nel secondo in base al criterio della soccombenza a danno dell'appellante". La conclusione pretorile secondo cui le poste rivendicate non sono qualificabili come danno risarcibile ai sensi dell'<ref-law> è stata pertanto confermata.
D. Prevalendosi della violazione dell'<ref-law>, rispettivamente della sua applicazione arbitraria, il 14 dicembre 2009 A._ ha inoltrato al Tribunale federale un ricorso in materia civile e costituzionale sussidiario volto a ottenere, in via principale, la modifica della decisione impugnata nel senso dell'accoglimento del suo appello e, di conseguenza, del riconoscimento del suo diritto a fr. 27'401.20, oltre interessi, a titolo di risarcimento danni e al versamento di fr. 12'169.40 per ripetibili della prima sede. In via subordinata ha postulato il rinvio degli atti all'autorità cantonale per nuova decisione ai sensi dei considerandi.
Con risposta del 29 gennaio 2010 B._ SA ha proposto di dichiarare il ricorso in materia civile inammissibile, rispettivamente di respingerlo nella misura in cui dovesse essere ritenuto ammissibile. Nell'eventualità in cui venisse vagliato il ricorso sussidiario in materia costituzionale, essa propone di respingerlo in quanto ammissibile.
L'autorità cantonale non ha invece formulato alcuna osservazione, riconfermandosi nelle motivazioni e conclusioni contenute nella sentenza impugnata.

Diritto:
1. Il Tribunale federale si pronuncia d'ufficio e con pieno potere d'esame sulla propria competenza e sull'ammissibilità del rimedio (<ref-law>; <ref-ruling> consid. 1.1 pag. 3).
1.1 Consapevole del mancato raggiungimento del valore litigioso minimo di fr. 30'000.-- prescritto dall'<ref-law>, il ricorrente ritiene di poter ciononostante introdurre un ricorso in materia civile in forza dell'<ref-law>, per il motivo che la controversia concerne una "questione di diritto d'importanza fondamentale".
1.1.1 Egli reputa infatti "opportuno ed urgente che il Tribunale federale stabilisca delle regole chiare in merito ai risarcimenti che si possono ottenere, in particolare per la rifusione delle spese giudiziarie e legali", in caso di una procedura (esecutiva) abusiva. Sollecita segnatamente una decisione sulla questione di sapere "se le spese legali sostenute nell'ambito di una procedura che, secondo il diritto federale (LEF/OTLEF), è gratuita e non prevede l'attribuzione di ripetibili, possono essere fatte valere a titolo di risarcimento danni ex <ref-law>" e, secondariamente, sulla questione di sapere "quali tasse e spese di giustizia, nonché ripetibili e spese legali, sostenute nell'ambito di procedimenti giudiziari finalizzati all'annullamento dell'indebita esecuzione possono essere fatte valere successivamente nell'ambito di un'azione di risarcimento danni ex <ref-law>". Questo "alfine di non indurre le vittime di abusi esecutivi a rinunciare ad adire i tribunali, avallando così le manovre di chi ricorre a questi sistemi pur di ottenere sconti non dovuti, o l'abbandono di pretese più che legittime".
1.1.2 Secondo la giurisprudenza sviluppata dal Tribunale federale la nozione di "questione di diritto d'importanza fondamentale" dev'essere interpretata in maniera molto restrittiva (<ref-ruling> consid. 1.1). Le situazioni nelle quali l'esistenza di una tale questione è già stata ammessa sono elencate nella <ref-ruling> (consid. 1.3 pag. 4); in sintesi, è considerata questione di diritto d'importanza fondamentale quella che crea una situazione d'incertezza giuridica tale da rendere urgentemente necessario un chiarimento da parte del Tribunale federale (<ref-ruling> consid. 1.2 pag. 399).
Contrariamente a quanto asseverato nel gravame, questa eventualità non si verifica nella fattispecie. Le questioni sollevate dal ricorrente non creano situazioni d'incertezza giuridica e possono essere decise mediante l'applicazione dei principi giurisprudenziali già noti, posti nella <ref-ruling>, e delle regole sulla responsabilità per atto illecito (art. 41 segg. CO). Questo comporta l'inammissibilità, d'acchito, del ricorso in materia civile.
1.2 Contro la sentenza emanata il 21 ottobre 2009 dalla II Camera civile del Tribunale d'appello del Cantone Ticino è dunque proponibile solo il ricorso sussidiario in materia costituzionale (art. 113 segg. LTF).
Interposto tempestivamente (<ref-law>) dalla parte soccombente in sede cantonale (<ref-law>) contro una decisione finale (<ref-law>) pronunciata dall'autorità ticinese di ultima istanza (art. 114 con rinvio all'<ref-law>), il ricorso è ricevibile.
2. Con il ricorso in materia costituzionale può unicamente essere censurata la violazione dei diritti costituzionali (<ref-law>), secondo le modalità stabilite nell'<ref-law> (<ref-law>).
Se, come nella fattispecie in esame, viene invocata la violazione del divieto dell'arbitrio, la parte ricorrente 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. Per giurisprudenza invalsa, infatti, l'arbitrio non si realizza già qualora la soluzione proposta con il ricorso possa apparire sostenibile o addirittura migliore rispetto a quella contestata; il Tribunale federale annulla la pronunzia criticata per violazione dell'<ref-law> solo se il giudice del merito ha emanato un giudizio che appare - e ciò non solo nella sua motivazione bensì anche nell'esito - manifestamente insostenibile, in aperto contrasto con la situazione reale, gravemente lesivo di una norma o di un principio giuridico chiaro e indiscusso, oppure in contraddizione urtante con il sentimento della giustizia e dell'equità (<ref-ruling> consid. 1.3 pag. 4; <ref-ruling> consid. 3.1 pag. 265 seg.).
3. Contrariamente a quanto asseverato nel gravame, la decisione impugnata resiste alla censura di arbitrio. Essa non disattende i principi stabiliti nella <ref-ruling>, non viola gravemente i principi sul risarcimento del danno né conduce a un risultato in contraddizione urtante con il sentimento di giustizia ed equità.
3.1 Al di là delle regole che vigono in materia di risarcimento dei costi preprocessuali e processuali in generale e, più specificatamente, nel caso in cui l'atto illecito sia rappresentato dalla condotta processuale stessa - pertinentemente riassunte al consid. 4 della sentenza cantonale, a cui si può rinviare in virtù dell'<ref-law> - va infatti ricordato che, condizione essenziale per il risarcimento delle spese legali giusta l'<ref-law> è, in ogni caso, che l'assistenza legale sia giustificata, necessaria e appropriata (<ref-ruling> consid. 6b pag. 107; cfr. Roland Brehm in Berner Kommentar n. 87 ad <ref-law>). Tocca alla parte che postula il risarcimento dei costi d'avvocato allegare e dimostrare che tale condizione è soddisfatta.
3.2 Questo requisito non è adempiuto per le spese d'avvocato affrontate dal ricorrente in relazione alla procedura di ricorso ex art. 17-19 LEF al Bezirkgericht di Zurigo.
La Corte cantonale sembra invero voler escludere in maniera assoluta la possibilità di ottenere il rimborso di tali costi - anche in presenza di un'esecuzione abusiva - a causa del carattere gratuito della procedura di ricorso (<ref-law>), nell'ambito della quale non vengono assegnate indennità per ripetibili (art. 62 cpv. OTLEF). A mente del ricorrente questa tesi è arbitraria. La questione può rimanere irrisolta, giacché nella fattispecie la decisione dei giudici ticinesi di negare il rimborso di tali costi appare in ogni caso sostenibile nel risultato. L'eventuale natura abusiva dell'esecuzione posta in atto dall'opponente non dispensava infatti il ricorrente dall'onere di allegare (e dimostrare) la sussistenza degli ulteriori requisiti posti all'applicazione dell'<ref-law>, in particolare con riferimento alla necessità dell'intervento del legale nella procedura di ricorso in rassegna. Giovi ricordare che la procedura di ricorso ex art. 17-19 LEF è una procedura retta dalla massima ufficiale, che non richiede di regola la partecipazione di un avvocato, salvo in presenza di una fattispecie complessa, che in concreto non è ravvisabile (consid. B.a e B.b) né tantomeno è stata allegata (<ref-ruling> consid. 2c pag. 10).
3.3 Alla stessa conclusione deve giungere per i costi della causa di accertamento negativo promossa dinanzi al tribunale zurighese, dichiaratosi territorialmente incompetente.
Quand'anche l'esecuzione promossa dall'opponente fosse da reputarsi illecita, l'introduzione di una causa dinanzi a un foro incompetente non configurava uno strumento giustificato, necessario e adeguato alla salvaguardia dei diritti del ricorrente. Nulla muta l'asserito carattere discutibile della decisione zurighese; il ricorrente avrebbe potuto e dovuto, se del caso, far valere questo argomento nei tempi e nei modi previsti dalla normativa processuale applicabile.
4. In conclusione, il ricorso in materia civile dev'essere dichiarato inammissibile mentre il ricorso sussidiario in materia costituzionale va respinto siccome infondato.
Le spese giudiziarie e le ripetibili della sede federale seguono la soccombenza e sono pertanto poste a carico del ricorrente (art. 66 cpv. 1 e 68 cpv. 1 e 2 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Il ricorso in materia civile è inammissibile.
2. Il ricorso sussidiario in materia costituzionale è respinto.
3. Le spese giudiziarie di fr. 2'000.-- sono poste a carico del ricorrente, il quale rifonderà all'opponente fr. 2'500.-- per ripetibili della sede federale.
4. Comunicazione ai patrocinatori delle parti e alla II Camera civile del Tribunale d'appello del Cantone Ticino.