Sachverhalt:
A. Am 15. September 2005 erstattete X._ Strafanzeige gegen Y._, weil er ihn verdächtigte, diverse Lithographien aus seinem Basler Tresor gestohlen und weiter verkauft zu haben.
B. Nach zwei Hausdurchsuchungen beim Beschuldigten und diversen Einvernahmen (darunter zwei Konfrontationseinvernahmen) stellte die Staatsanwaltschaft Basel-Stadt das Verfahren gegen Y._ am 29. Juli 2009 ein. Sie war zum Schluss gelangt, es könne nicht rechtsgenüglich nachgewiesen werden, dass der Beschuldigte die dem Anzeigeerstatter gehörenden Gegenstände aus dessen Safe weggeschafft und an einen seiner Wohnorte verbracht habe. Zwischen den Beiden bestehe ein vielfältiges Geflecht geschäftlicher, zwischenmenschlicher und persönlicher Beziehungen. Für die angeblichen Diebstahlshandlungen gebe es keine Tatzeugen.
C. Die Rekurskammer des Strafgerichts Basel-Stadt schützte diesen Einstellungsbeschluss mit Urteil vom 28. Dezember 2010 und wies einen von X._ dagegen eingereichten Rekurs ab.
D. Am 9. Mai 2011 erhebt X._ Beschwerde in Strafsachen ans Bundesgericht. Er verlangt, der Entscheid der Rekurskammer des Strafgerichts sei aufzuheben und die Sache zur neuen Entscheidung an die Vorinstanz zurückzuweisen. Weiter sei die Vorinstanz anzuweisen, die Sache an die Staatsanwaltschaft zur weiteren Strafuntersuchung und Anklageerhebung zurückzuweisen. Gleichzeitig ersucht der Beschwerdeführer um Gewährung der aufschiebenden Wirkung.
E. Y._ ersuchte hierauf am 26. Mai 2011 um Sistierung des bundesgerichtlichen Verfahrens, weil die Parteien inzwischen ein Mediationsverfahren angestrengt hätten, in welchem primär zivilrechtliche Forderungen behandelt werden sollten. Da von keiner Seite Einwände erhoben wurden, sistierte der Instruktionsrichter der I. öffentlich-rechtlichen Abteilung das Beschwerdeverfahren am 21. Juni 2011 bis längstens 15. September 2011. Nach erfolglosem Ablauf dieser Frist resp. nach Scheitern der Mediationsbemühungen wurde das Verfahren mit Verfügung vom 16. September 2011 wieder aufgenommen.
Y._ als Beschuldigter und privater Beschwerdegegner schliesst auf Nichteintreten, eventualiter auf Abweisung der Beschwerde. Die Staatsanwaltschaft des Kantons Basel-Stadt stellt ebenfalls Antrag auf Abweisung. Auch die Rekurskammer des kantonalen Strafgerichts beantragt, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne.
In einer weiteren Eingabe hält der Beschwerdeführer sinngemäss an seinen Anträgen fest.

Erwägungen:
1. Das angefochtene Urteil bestätigt, dass das vom Beschwerdeführer angestrebte Strafverfahren nicht eröffnet wird. Es schliesst damit das Verfahren ab. Es handelt sich um den Endentscheid einer letzten kantonalen Instanz in einer Strafsache, gegen den die Beschwerde in Strafsachen zulässig ist (Art. 78 Abs. 1, Art. 80 Abs. 1 und Art. 90 BGG).
2. 2.1 Der erste Entscheid in dieser Sache erging am 10. Dezember 2010 nach der bis Ende 2010 in Kraft stehenden Strafprozessordnung des Kantons Basel-Stadt vom 8. Januar 1997 (StPO/BS). Am 1. Januar 2011 trat die Schweizerische Strafprozessordnung vom 5. Oktober 2007 (SR 312.0; StPO) in Kraft (AS 2010 1881), welche die kantonalen Strafprozessordnungen ablöst. Nach der einschlägigen Übergangsbestimmung von <ref-law> ist auf Rechtsmittel gegen vor dem 1. Januar 2011 gefällte Entscheide das bisherige Recht anwendbar. Die Rekurskammer des Strafgerichts beurteilte die Beschwerde am 28. Dezember 2010 daher zu Recht nach den Bestimmungen der StPO/BS, welche auch für die vorliegende Beschwerde massgebend sind (<ref-law>; vgl. das Urteil 1B_188/2011 des Bundesgerichts vom 1. Juni 2011 E. 1.2).
2.2 Der Beschwerdeführer beruft sich auf <ref-law> und macht geltend, er sei als Privatkläger zu betrachten. Er habe am vorinstanzlichen Verfahren teilgenommen und habe zufolge der Freigabe von Gegenständen, bezüglich denen er Eigentumsansprüche geltend mache, ein rechtlich geschütztes Interesse an der Aufhebung des angefochtenen Entscheids. Zudem könne sich der angefochtene Entscheid auf seine zivilrechtlichen Ansprüche gegen den Beschwerdegegner auswirken.
2.3 Da der angefochtene Entscheid vor dem 31. Dezember 2010 gefällt wurde, beurteilt sich die Frage des rechtlich geschützten Interesses nach der dannzumal geltenden Fassung von aArt. 81 Abs. 1 lit. b Ziff. 5 BGG. Danach wurde nicht die Privatklägerschaft schlechthin, sondern nur das Opfer als beschwerdelegitimiert bezeichnet; dies ebenfalls unter der Voraussetzung, dass sich der angefochtene Entscheid auf die Beurteilung seiner Zivilansprüche auswirken kann (Urteil 1B_236/2011 vom 15. Juli 2001 E. 1.3.1; <ref-ruling> E. 1.1.1 S. 196 f.).
2.4 Zwar ist nachvollziehbar, dass die Freigabe der Lithografien Auswirkungen auf die zivilrechtlichen Ansprüche des Beschwerdeführers haben soll. Opfer im Sinne von <ref-law> ist aber nur, wer durch eine Straftat in seiner körperlichen, sexuellen oder psychischen Integrität unmittelbar beeinträchtigt worden ist. Es ist nicht ersichtlich und wurde auch nicht rechtsgenüglich dargetan, dass der Beschwerdeführer diese Voraussetzungen erfüllen würde.
2.5 Trotz fehlender Legitimation in der Sache konnte der Beschwerdeführer indessen in jedem Fall die auf eine formelle Rechtsverweigerung hinauslaufende Verletzung von Parteirechten rügen ("Star-Praxis"; <ref-ruling> E. 6.2 S. 198). Eine solche macht der Beschwerdeführer nicht explizit geltend. Selbst wenn dem so wäre, wäre die Beschwerde aber abzuweisen, wie die nachfolgenden Erwägungen zeigen.
3. Nach <ref-law>/BS verfügt die Staatsanwaltschaft die Einstellung des Verfahrens und entscheidet, wer die Verfahrenskosten zu tragen hat, wenn die Ermittlungen ergeben, dass zureichende Gründe für die Erhebung einer Anklage fehlen oder gemäss <ref-law> auf die Verfolgung einer strafbaren Handlung zu verzichten ist.
3.1 Wie die Rekurskammer des Strafgerichts im angefochtenen Urteil ausführlich aufzeigt, bestand zwischen dem Anzeigeerstatter und dem Beschuldigten eine komplexe geschäftliche und private Beziehung. Zwar schliesst dies strafrechtlich relevantes Verhalten nicht aus. Die diversen Einvernahmen und widersprüchlichen Aussagen von beiden Seiten machen aber deutlich, wie verworren die Situation zwischen den Parteien ist. So ergab sich im Verlaufe des Verfahrens, dass der Anzeigeerstatter den Beschuldigten entgegen seinen eigenen Angaben verschiedene Male beschenkt hatte. Auch der Beschuldigte muss sich Ungereimtheiten vorhalten lassen, insbesondere, was den Lithografien-Verkauf an die Kölner Galerie anbelangt. Hinzu kommt erschwerend der Zeitfaktor: Der Anzeigeerstatter ist erst fünf Jahre nach Entdecken des Verlusts an die Polizei gelangt, was die Rekonstruktion der Vorkommnisse zusätzlich erschwert. Insgesamt kann auf die zutreffenden Erwägungen der Vorinstanz verwiesen werden (<ref-law>). Es ist den kantonalen Behörden nicht vorzuwerfen, wenn sie aufgrund der dürftigen Beweis- beziehungsweise Indizienlage das Verfahren eingestellt haben. Der Grundsatz "in dubio pro duriore" wird dadurch nicht verletzt (dazu <ref-ruling> E. 7.1 S. 226).
3.2 Das angefochtene Urteil genügt den Begründungsanforderungen denn auch bei Weitem. Die entsprechende Rüge des Beschwerdeführers ist abzuweisen, werden die entscheidrelevanten Faktoren von der Rekurskammer doch deutlich dargelegt. Weitere Ausführungen waren nicht notwendig. Desgleichen ist der Vorinstanz kein Vorwurf wegen Gehörsverletzung zu machen. Der Beschwerdeführer kann aus dem Umstand, dass die Rekurskammer die Rechtslage anders beurteilt als er, keine Ansprüche ableiten.
4. Auf die Beschwerde ist demnach nicht einzutreten. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kostenpflichtig (<ref-law>). Zudem hat er den Beschuldigten als privaten Beschwerdegegner für das bundesgerichtliche Verfahren angemessen zu entschädigen.

Demnach erkennt das Bundesgericht:
1. Auf die Beschwerde wird nicht eingetreten.
2. Die Gerichtskosten von Fr. 1'500.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat den privaten Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 1'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Staatsanwaltschaft des Kantons Basel-Stadt und dem Strafgericht Basel-Stadt, Rekurskammer, schriftlich mitgeteilt.
Lausanne, 11. November 2011
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Scherrer Reber