Sachverhalt: A. X._ ersuchte die IV-Stelle Basel-Stadt am 10. Oktober 2006 um Vernichtung eines Arztberichts von Dr. med. O._, den dieser am 4. Januar 2002 der IV-Stelle Basel-Stadt erstattet hatte (im Folgenden "Bericht O._"). Eventualiter beantragte der Gesuchsteller das Anbringen von Bestreitungsvermerken hinsichtlich des Berichts O._. Die IV-Stelle wies die Begehren mit Verfügung vom 19. April bzw. vom 26. April 2007 ab. Das Sozialversicherungsgericht Basel-Stadt trat auf einen Rekurs von X._ nicht ein. Dieser gelangte an das Wirtschafts- und Sozialdepartement Basel-Stadt (WSD). Dieses hiess den Rekurs am 20. Oktober 2008 teilweise gut. Es wies das Ersuchen um Vernichtung bzw. Berichtigung des Berichts O._ zwar ab, hielt die IV-Stelle indes an, die gesamten Verfahrensunterlagen im Sinne einer Gegendarstellung zu den IV-Akten zu nehmen. Im Übrigen wies es den Rekurs ab. In der Folge erhob X._ Rekurs beim Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht). Dieses wies den Rekurs am 26. März 2009 ab, soweit darauf einzutreten war. B. Gegen dieses Urteil des Appellationsgerichts hat X._ beim Bundesgericht am 16. Juni 2009 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Er beantragt im Wesentlichen die Aufhebung des angefochtenen Entscheides sowie die Vernichtung des Berichts O._ und die Unkenntlichmachung verschiedener Stellen in den Akten. Überdies stellt er weitere Begehren. Die IV-Stelle verzichtet auf eine Stellungnahme und beantragt Abweisung der Beschwerde. Das Departement für Wirtschaft, Soziales und Umwelt sowie das Appellationsgericht beantragen, es sei die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Der Beschwerdeführer hält in seiner Replik an seinen Anträgen fest und ergänzt seine Begründung.