Faits : A. Les époux A.X._ et B.X._ sont en litige conjugal depuis plusieurs années. Diverses procédures judiciaires ont été engagées de part et d'autre sur les plans civil et pénal. Le 21 octobre 2014, A.X._ a déposé une plainte pénale contre son épouse B.X._ pour contrainte (art. 181 CP). Il lui reprochait, en substance, d'avoir subordonné une rencontre avec leur fils commun C.X._, né en 1996, à l'exécution de diverses obligations, dont le paiement d'une somme de 40'000 fr. au titre de provision ad litem. B. Par ordonnance du 28 octobre 2014, le Ministère public du canton de Genève a refusé d'entrer en matière sur la plainte pénale au motif notamment que le fait de subordonner un contact avec C.X._ à l'exigence du paiement de 40'000 fr. ou aux autres termes du courrier - obligations au demeurant exécutoires selon un arrêt de la Cour de justice du canton de Genève du 11 avril 2014 statuant sur les mesures protectrices de l'union conjugale -, ne constituait pas un acte de contrainte grave, assimilable à l'usage de la violence ou à la menace d'un dommage sérieux. C. La Chambre pénale de recours du canton de Genève a rejeté le recours formé par A.X._ contre l'ordonnance de non-entrée en matière et confirmé cette dernière, par arrêt du 10 mars 2015. Elle a alloué à B.X._ un montant de 5'000 fr. à la charge de A.X._, à titre d'indemnité pour les dépenses occasionnées par l'exercice raisonnable de ses droits de procédure. D. A.X._ interjette un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut à son annulation, respectivement à l'annulation de l'ordonnance de non-entrée en matière et au renvoi de la cause au Ministère public pour qu'il instruise les faits découlant de la plainte pénale. Subsidiairement, il conclut au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Invité à se déterminer sur la question de l'indemnité de 5'000 fr., le Ministère public a conclu au rejet du recours et a formulé de brèves observations. Pour sa part, la cour cantonale a déclaré ne pas avoir d'observations à formuler. L'intimée a conclu au rejet du recours, en justifiant la quotité de l'indemnité lui étant allouée.