Sachverhalt: A. Die Versicherung Y._ und ab 2003 die Versicherung X._ AG (Beschwerdegegnerin) haben A._ (Beschwerdeführer) in Basel eine Wohnung vermietet. Das Mietverhältnis dauerte von 1987 bis 2009. Der ursprüngliche Mietzins von Fr. 760.-- wurde einmal gesenkt und mehrmals erhöht. Die letzte Mietzinsänderung per 1. April 2003 datiert vom 13. November 2002, das Begleitschreiben vom 15. November 2002. Im Gegensatz zu allen früheren Mietvertragsänderungsanzeigen ist jene vom 13. November 2002 vermieterseitig nicht handschriftlich unterzeichnet, sondern sie trägt lediglich faksimilierte Unterschriften der Vertreter der Vermieterin. Unter Berufung darauf machte der Beschwerdeführer am 15. Juli 2009 gegenüber der Vermieterschaft geltend, die Mietzinserhöhung per 1. April 2003 sei mangels eigenhändiger Unterzeichnung nichtig, weshalb er im Umfang dieser Erhöhung die Rückerstattung der bereits bezahlten Mietzinse beanspruche. Ausserdem verlangte er die Rückzahlung der von ihm bezahlten Nebenkosten für Wasser, Abwasser und Betriebskosten, da diese mangels besonderer Vereinbarung nicht geschuldet seien. B. Der Beschwerdeführer klagte am 23. November 2009 beim Zivilgericht Basel-Stadt mit dem Begehren, die Beschwerdegegnerin zu verpflichten, ihm die per 1. April 2003 erhöhten und bereits bezahlten Mieten im Gesamtbetrag von Fr. 13'746.-- zurück zu erstatten ebenso die von ihm bezahlten Nebenkosten für Wasser, Abwasser und Betriebskosten für den Zeitraum von 10 Jahren im Gesamtbetrag von Fr. 4'428.--. Das Zivilgericht wies die Klage am 23. März 2010 ab. Die gegen dieses Urteil eingereichte Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt am 14. April 2011 ab. C. Der Beschwerdeführer beantragt dem Bundesgericht mit Beschwerde in Zivilsachen, das Urteil des Appellationsgerichts aufzuheben und die Beschwerdegegnerin zur Zahlung von Fr. 18'174.-- nebst Zins zu verpflichten. Die Beschwerdegegnerin schliesst auf kostenfällige Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Appellationsgericht verweist auf die Erwägungen im angefochtenen Urteil und geht auf Ausführungen des Beschwerdeführers ein, die es als verkürzt oder verzerrt erachtet. Dieser hat eine Replik eingereicht.