Faits : A. Après avoir été interpellé le 12 avril 2015, A._ a été mis en prévention pour menaces (art. 180 CP), tentative d'actes d'ordre sexuel sur des enfants (art. 198 ch. 2 CP), pornographie aggravée (art. 197 ch. 3bis aCP et art. 197 ch. 5 CP) et utilisation abusive d'une installation de télécommunication (art. 179septies CP). Il lui est en substance reproché d'être l'auteur d'appels téléphoniques anonymes à des jeunes filles dont il avait trouvé les identités et photographies sur des sites de course pédestre, lors desquels il formulait des menaces et tenait des propos obscènes à caractère sexuel. Invoquant les risques de collusion et réitération, le Ministère public a requis la mise en détention provisoire de l'intéressé pour une durée de trois mois. Non astreint à y participer, le Ministère public n'était pas présent à l'audience que le Tribunal des mesures de contrainte de la République et canton de Genève (Tmc) a tenue le 15 avril 2015. B. A l'issue de son audience, le Tmc a rejeté la demande de mise en détention provisoire du Ministère public et ordonné la libération du prévenu à la condition expresse qu'il respecte des mesures de substitution détaillées, fixées pour une durée de six mois. Cette ordonnance a été rendue par le Tmc à 11h41 et notifiée immédiatement au prévenu. En réponse à un e-mail que le greffe de la prison lui a adressé à 12h14, le Ministère public a informé celui-ci de son intention de faire recours contre cette ordonnance par un e-mail envoyé à 12h31. Le Ministère public a ensuite expédié son acte de recours au greffe de la Chambre pénale de recours de la Cour cantonale de justice à 13h46 par messagerie sécurisée et l'a déposé au guichet de cette instance à 14h00 le même jour. Par arrêt du 29 avril 2015, la cour cantonale a admis le recours du Ministère public, annulé l'ordonnance entreprise et ordonné la mise en détention provisoire du prévenu jusqu'au 15 juillet 2015. C. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler cet arrêt, d'ordonner sa mise en liberté immédiate, à charge pour le Ministère public d'en organiser sans délai les modalités, et de confirmer l'ordonnance de mise en liberté avec mesures de substitution rendue le 15 avril 2015 par le Tmc. Il conclut subsidiairement à l'annulation de l'arrêt et au renvoi de l'affaire devant l'instance précédente pour nouvelle décision au sens des considérants. Il produit deux nouvelles pièces qui ne figuraient pas au dossier lorsque la cour cantonale a statué. Dans ses observations, la cour cantonale indique maintenir les termes de son arrêt et, vu les nouvelles pièces, précise s'en remettre à l'appréciation du Tribunal fédéral quant au sort de la cause. Le Ministère public conclut au rejet du recours. Le recourant réplique et persiste dans ses conclusions.