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.

Erwägungen:
1. Da der erstinstanzliche Entscheid den Parteien am 23. März 2010 und damit vor Inkrafttreten der Eidgenössischen Zivilprozessordnung eröffnet wurde, richtete sich das Rechtsmittelverfahren vor der Vorinstanz noch nach der Zivilprozessordnung des Kantons Basel-Stadt vom 8. Februar 1875 (<ref-law>; <ref-ruling>).
2. Die Vorinstanz erkannte, das Formular zur Anzeige der Mietzinserhöhung per 1. April 2003 vom 13. November 2002 weise lediglich die faksimilierten Unterschriften von B._ und C._ auf, weshalb diese Erhöhungsanzeige grundsätzlich nichtig sei. In Anwendung der sozialen Untersuchungsmaxime gemäss <ref-law> stellte die Vorinstanz allerdings fest, das Begleitschreiben zur Mietzinserhöhung per 1. April 2003 vom 15. November 2002 sei von B._ und C._ handschriftlich unterzeichnet. Aufgrund der eigenhändigen Unterzeichnung des Begleitschreibens sei im konkreten Fall der Formularpflicht gemäss <ref-law> Genüge getan und die Mietzinserhöhung als formgültig angezeigt zu betrachten. Als Eventualbegründung fügte die Vorinstanz an, die Rückforderung der bezahlten Mietzinse wäre auch wegen offenbaren Rechtsmissbrauchs ausgeschlossen. Kenntnis des Formmangels bilde nach der Rechtsprechung des Bundesgerichts (<ref-ruling> E. 3d S. 75) keine notwendige Voraussetzung hiefür. Nachdem der Beschwerdeführer die Mietzinse während mehr als 6 Jahren vorbehaltlos bezahlt habe, obwohl er über die Möglichkeit der Anfechtung der Mietzinserhöhung gehörig informiert und keinem Druck unterworfen gewesen sei, habe die Beschwerdegegnerin keinen Anlass gehabt, an der Gültigkeit der Mietzinserhöhung zu zweifeln und deren Anzeige zu wiederholen. Zudem lägen keinerlei Anhaltspunkte vor, die für die Missbräuchlichkeit des erhöhten Mietzinses sprächen. Die Klage auf Rückforderung des bezahlten Mietzinses müsste daher auch an <ref-law> scheitern.
2.1 Der Beschwerdeführer bestreitet, dass der Begleitbrief handschriftlich unterzeichnet sei. Er rügt eine offensichtlich unrichtige Feststellung des Sachverhalts und eine Verletzung seines Anspruchs auf rechtliches Gehör. Zudem verstosse die Vorinstanz willkürlich gegen das massgebende kantonale Prozessrecht, indem sie den Sachverhalt von Amtes wegen ergänze. Schliesslich vermöge auch die Heranziehung des Begleitbriefes die Formungültigkeit nicht zu heilen. Diese Rügen brauchen indessen nicht behandelt zu werden, sofern die Mietzinse zufolge Rechtsmissbrauchs ohnehin nicht zurückgefordert werden können. Zu prüfen ist daher zunächst, ob der Beschwerdeführer die Formungültigkeit der Mietzinserhöhung rechtsmissbräuchlich geltend gemacht hat.
2.2 Die Vorinstanz erkannte zutreffend, dass die Frage, ob die Berufung auf Formnichtigkeit einen offenbaren Rechtsmissbrauch darstellt, nach der Rechtsprechung in Würdigung aller Umstände des konkreten Falles zu prüfen ist. Massgebend ist namentlich das Verhalten der Parteien bei und nach Abschluss des Vertrags. Die Geltendmachung eines Rechts ist missbräuchlich, wenn sie im Widerspruch zu einem früheren Verhalten steht und dadurch erweckte berechtigte Erwartungen enttäuscht (<ref-ruling> E. 5.1 S. 497). Widersprüchliches Verhalten kann aber auch ohne Enttäuschung berechtigter Erwartungen in einer gegenwärtigen, in sich völlig unvereinbaren und darum widersprüchlichen Verhaltensweise gesehen werden. Missbräuchlich ist ferner die Rechtsausübung, die ohne schützenswertes Interesse erfolgt oder zu einem krassen Missverhältnis berechtigter Interessen führen würde. Rechtsmissbrauch liegt auch vor, wenn ein Rechtsinstitut zweckwidrig zur Verwirklichung von Interessen verwendet wird, die nicht in dessen Schutzbereich liegen (<ref-ruling> E. 4.3 S. 629; <ref-ruling> E. 3.3.1 S. 169; <ref-ruling> E. 5 S. 252).
2.3 Die Vorinstanz erachtete die Anrufung des Formmangels für missbräuchlich und schützte aufgrund der vorbehaltlosen Zahlungen des Beschwerdegegners das Vertrauen der Beschwerdegegnerin in die Gültigkeit der Mietzinserhöhung.
2.3.1 Nach der Rechtsprechung verhält sich rechtsmissbräuchlich, wer einen Vertrag freiwillig, irrtumsfrei und mindestens zur Hauptsache erfüllt hat und hernach den Restanspruch der Gegenpartei unter Verweis auf den Formmangel verweigert (<ref-ruling> E. 3b S. 702; <ref-ruling> E. 3c S. 112, 330 E. 2 S. 332 ff. vgl. auch <ref-ruling> E. 4 S. 512 ff.). "Irrtumsfrei" bedeutet in diesem Fall in Kenntnis des Formmangels. Die Berufung auf den Formmangel kann grundsätzlich nur unstatthaft sein, wenn die Parteien bei Abschluss und Erfüllung des Vertrags wussten oder in zurechenbarer Weise wissen konnten, dass das durch sie getätigte Rechtsgeschäft der gesetzlichen Formpflicht widerspricht. Wer einen formnichtigen Vertrag freiwillig erfüllt, ohne den Mangel zu kennen, verhält sich nicht widersprüchlich und handelt folglich auch nicht missbräuchlich, wenn er sich nachträglich wegen des Mangels auf Nichtigkeit beruft. Das gilt selbst dann, wenn angenommen wird, die beidseitige Erfüllung des Vertrages heile den Formmangel, mache also nicht nur dessen Anrufung missbräuchlich (<ref-ruling> E. 2b S. 334 mit Hinweisen).
2.3.2 Rechtsmissbräuchlich kann allerdings handeln, wer mit der Klageanhebung zuwartet, um sich später aus der Berufung auf Nichtigkeit Vorteile zu verschaffen (<ref-ruling> E. 5.1 S. 498; <ref-ruling> E. 3c S. 75). Im zuletzt genannten Entscheid, auf den sich die Vorinstanz wesentlich abstützt, hob das Bundesgericht hervor, dass die an sich formungültige Mietzinserhöhung nicht ohne vorgängige Verhandlungen zustande gekommen sein konnte, zumal sie in einem Nachtrag zum Mietvertrag vereinbart worden war, in dessen Rahmen die Vermieterschaft auf das Recht, auf einen früheren Termin zu kündigen, und auf die ursprünglich vereinbarte Umsatzbeteiligung verzichtet hatte. Nach jahrelanger anstandsloser Fortführung des Mietverhältnisses hätten sich die geschäftserfahrenen Mieter erst auf die Formungültigkeit der neun Jahre zuvor erfolgten Mietzinserhöhung berufen, nachdem sie mit der neuen Eigentümerin des Mietobjekts über die Bedingungen einer Weiterführung des Mietverhältnisses Verhandlungen aufgenommen hatten, welche aber für die Mieter nicht befriedigend verliefen. Weil die Mieter mit diesem Verhalten bei der Vermieterschaft das begründete Vertrauen erweckt hatten, die Vereinbarung über die Geschäftsmiete sei gültig, erachtete das Bundesgericht die Berufung auf den Formmangel als missbräuchlich.
2.3.3 Mit dieser Konstellation weist die vorliegend zu beurteilende, wie der Beschwerdeführer zu Recht einwendet, kaum Analogien auf. Als zu berücksichtigender Umstand fällt nach dem angefochtenen Urteil einzig ins Gewicht, dass der Mieter den erhöhten, mutmasslich nicht missbräuchlichen Mietzins während mehr als sechs Jahren trotz gehöriger Information über die Anfechtungsmöglichkeit auf dem Formular und ohne unter Druck gestanden zu sein, vorbehaltlos bezahlt hat. Nach der Rechtsprechung des Bundesgerichts genügt indessen die blosse Erfüllung eines formungültigen Rechtsgeschäfts als solche, wenn sie in Unkenntnis des Formmangels erfolgt, nicht zur Begründung berechtigten Vertrauens der Gegenpartei in die Gültigkeit des Rechtsgeschäfts (vgl. <ref-ruling> E. 1b S. 189).
2.4 Damit bleibt zu prüfen, ob das Verhalten des Beschwerdeführers allenfalls auch ohne Erweckung berechtigten Vertrauens missbräuchlich erscheint.
2.4.1 Missbräuchlich handelt, wie dargelegt (E. 2.2 hiervor), wer ein Rechtsinstitut zweckwidrig zur Verwirklichung von Interessen verwendet, die dieses Rechtsinstitut nicht schützen will (<ref-ruling> E. 2.2 S. 151 mit Hinweisen), d.h. wenn der Rückgriff auf das Rechtsinstitut mit dem angestrebten Zweck nichts zu tun hat oder diesen gar ad absurdum führt (HONSELL, in: Basler Kommentar, Zivilgesetzbuch, 4. Aufl. 2010, N. 51 zu <ref-law>). Besondere Umstände, welche die Berufung auf zwingendes Recht als missbräuchlich erscheinen lassen, sind auch zu bejahen, wenn die von der angerufenen Norm zu schützenden Interessen entfallen oder sonst wie gewahrt wurden (<ref-ruling> E. 5.1 S. 498 mit Hinweisen). Ob eine Berechtigung missbräuchlich ausgeübt wird, hängt wiederum von den Umständen des Einzelfalles ab (<ref-ruling> E. 4.3 S. 629; <ref-ruling> E. 3.3.1 S. 169).
2.4.2 Zweck der Formularpflicht ist primär die Information des Mieters über die Gründe der Erhöhung und die Anfechtungsmöglichkeiten. Es geht darum, ihm den Rechtsweg aufzuzeigen und ihm eine möglichst einfache Beurteilung seiner Chancen zu sichern, die angekündigte Mietzinserhöhung anzufechten (<ref-ruling> E. 1.5.3 S. 224 f.; <ref-ruling> E. 3b S. 217 mit Hinweisen). Diese Zwecke hat das dem Beschwerdeführer zugestellte Formular mit Bezug auf die Mietzinserhöhung zweifellos erfüllt. Diesbezüglich bedurfte es keiner eigenhändigen Unterschrift. Mit dem letztgenannten Erfordernis soll namentlich vermieden werden, dass die Identität des Erklärenden unsicher bleibt. Sie dient der Befriedigung des Bedürfnisses nach Zurechnung der Erklärung an eine eindeutig identifizierbare Person. Die eigenhändige Unterschrift der Vermieterschaft gewährleistet im Schriftverkehr grundsätzlich diese eindeutige Zurechnung. Aus diesem Grunde ist sie als wesentliches Element der Schriftlichkeit für die qualifizierte Schriftform des Formulars erforderlich, sofern nicht die - hier nicht gegebene - Ausnahme von <ref-law> Anwendung findet.
2.4.3 Dass jemals Unklarheit über den Absender bzw. die Zurechenbarkeit der Mietzinserhöhung geherrscht hätte, macht der Beschwerdeführer nicht geltend. Vielmehr richteten sich offenbar beide Parteien während Jahren anstandslos nach dem nicht handschriftlich unterzeichneten Formular, und es ist nicht festgestellt, dass die Beschwerdegegnerin sich die dem Beschwerdeführer gelieferte Begründung für die Mietzinserhöhung nicht hätte entgegenhalten lassen. Das Erfordernis handschriftlicher Unterzeichnung der Mietzinserhöhung soll aber nicht dazu dienen, dem Mieter zu ermöglichen, auf eine unangefochtene Mietzinserhöhung, deren Gültigkeit keine der Parteien anzweifelte und der nachgelebt wurde, nach Jahr und Tag zurückzukommen und den Differenzbetrag zurückzufordern, selbst wenn der diesbezügliche Mangel erst Jahre nach der Zustellung des im Übrigen nicht zu beanstandenden Erhöhungsformulars erkannt worden ist. Mit der Verfolgung eben dieses vom Formerfordernis nicht gedeckten Ziels übt der Beschwerdeführer sein Recht, sich auf einen Formmangel zu berufen, zweckwidrig und damit rechtsmissbräuchlich aus. Im Ergebnis erweist sich somit die Rechtsauffassung der Vorinstanz als mit <ref-law> vereinbar. Damit kann offenbleiben, ob das Begleitschreiben handschriftlich unterzeichnet ist und geeignet wäre, den Formmangel zu beheben. Auf die Kritik an den weiteren Erwägungen zur Frage der Gültigkeit der Mietzinserhöhung ist mangels Entscheidrelevanz nicht einzutreten.
3. Mit Blick auf die Nebenkosten kam die Vorinstanz zum Ergebnis, entgegen der Meinung des Beschwerdeführers sei die Tragung der Kosten für Wasser, Abwasser und Betrieb im Mietvertrag vom 7. Januar 1987 gültig vereinbart worden, weshalb sie das Begehren um deren Rückerstattung ablehnte.
3.1 Die Vorinstanz analysierte den Mietvertrag und erwog, als Nebenkosten würden in dessen Ziffer 2 lit. a) Heizkosten (mit dem Vermerk "akonto" und dem Betrag), b) Warmwasser (mit dem Vermerk "pauschal" und dem entsprechenden Betrag), d) Hauswartpauschale und e) Antenne aufgelistet. Zusätzlich finde sich unter lit. c eine Rubrik "Nebenkosten (s. Art. 7)", bei der kein Betrag eingesetzt und vom vorgedruckten Vermerk "akonto/pauschal" weder das eine noch das andere durchgestrichen sei. Ziff. 7 des Mietvertrages, auf den Ziff. 2 lit. c verweise, laute unter dem fett gedruckten Titel "Nebenkosten" wie folgt:
"Der Gas- und Stromverbrauch innerhalb der Mieträume geht zu Lasten des Mieters.
Wasser- und Abwassergebühren (ohne Grundgebühr), Kosten für Wasseraufbereitung oder -behandlung, Benützungs-Gebühren für Gemeinschafts-Antennenanlagen, ferner: [leer]
werden dem Mieter anteilsmässig belastet, gegebenenfalls über die Heiz- und/oder Nebenkostenabrechnung."
3.2 Dieser Regelung entnahm die Vorinstanz, Ziff. 2 des Mietvertrages stelle klar, dass Wasser- und Abwassergebühren vom Mieter als separat abzugeltende Nebenkosten anteilsmässig, also nicht pauschal, in Rechnung gestellt würden, ohne dass hierfür monatliche Akontobeträge erhoben würden. Diese Regelung bilde eine ausdrückliche Vereinbarung der Parteien im Sinne von <ref-law>, wonach der Mieter die betreffenden Gebühren entsprechend seinem Anteil gesondert schulde. Daran ändere auch die Anzeige einer Vertragsänderung vom 7. Dezember 1987 nichts, welche im Anschluss an die Ausführungen zur Erhöhung der Hauswartpauschale erwähne: "Andere Forderungen: Die Wasser- und Abwassergebühren werden ab 1. Mai 1988 zusammen mit der Heiz- und Nebenkostenabrechnung dem Mieter anteilmässig belastet." Damit werde einzig die bereits im Mietvertrag vorgesehene Regelung wiederholt und festgehalten, dass die Vermieterin davon Gebrauch mache, wovon damals auch der Beschwerdeführer ausgegangen sei.
3.3 Diese Würdigung ist im Lichte der bei der Vertragsauslegung nach dem Vertrauensprinzip zu beachtenden Grundsätze nicht zu beanstanden. Was der Beschwerdeführer vor Bundesgericht einwendet, verfängt nicht. Er hält sinngemäss daran fest, dass er nach Treu und Glauben bei Vertragsschluss davon habe ausgehen dürfen, die Wasser- und Abwasserkosten seien nicht separat geschuldet. Inwiefern der Hinweis gemäss Art. 2 lit. c des Mietvertrages auf dessen Art. 7 nicht genügen soll, um dem Mieter klar zu machen, dass er anteilsmässig mit Wasser- und Abwassergebühren belastet wird, zeigt der Beschwerdeführer jedoch nicht rechtsgenügend auf. Vielmehr ergeht er sich in allgemeinen Ausführungen und lässt den neben der Ziff. 7 des Vertrages fett gedruckten Titel "Nebenkosten" ausser Acht, wenn er darlegt, der Beschwerdeführer habe bei Vertragsschluss nicht gewusst und sei nicht zu Nachforschungen darüber verpflichtet gewesen, was "Art. 7" bedeute. Seine Kritik an der Vertragsauslegung der Vorinstanz ist offensichtlich unbegründet.
3.4 Gegen die Feststellung der Vorinstanz, auch er habe den Hinweis auf die Wasser- und Abwasserkosten in der Vertragsänderung vom 7. Dezember 1987 als Wiederholung der ursprünglichen Regelung verstanden, erhebt der Beschwerdeführer keine Willkürrüge. Er ist aber der Auffassung, er habe seinen Irrtum über die Leistungspflicht nachgewiesen, da dieser stets anzunehmen sei, wenn ausgeschlossen werden könne, dass der Leistende eine Schenkung beabsichtigte. Der Irrtum habe sich nicht auf die Richtigkeit der einzelnen Nebenkostenpositionen bezogen, sondern auf die Rechtsfrage, ob diese von der Vermieterschaft zu Recht verlangt würden. Mit seinen Vorbringen verkennt der Beschwerdeführer den Zusammenhang zwischen dem tatsächlichen Erkennen der einzelnen Nebenkostenpositionen und der Rechtsfolge der Zahlungspflicht. <ref-law> konkretisiert, soweit die Bestimmung übergangsrechtlich überhaupt auf vor ihrem Inkrafttreten abgeschlossene Mietverträge anzuwenden ist (die Vorinstanz liess die Frage offen), die allgemeine Auslegungsregel des <ref-law>, hebt sie aber nicht aus den Angeln. Demnach greift die objektivierte Vertragsauslegung nach dem Vertrauensprinzip nicht Platz, wenn sich die Parteien tatsächlich übereinstimmend verstanden und entsprechend geeinigt haben (vgl. <ref-ruling> E. 3.1 S. 632). Soweit der Mieter beim Abschluss des Vertrages tatsächlich erkennt, welche Nebenkosten ihm vertraglich aufgebürdet werden sollen, und den Vertrag in diesem Wissen unterzeichnet, ist <ref-law> Genüge getan, und der Mieter kann sich im Nachhinein nicht auf die fehlende Bestimmtheit des Vertragstextes berufen. Erkannte aber der Beschwerdeführer entsprechend der für das Bundesgericht verbindlichen Feststellung der Vorinstanz, dass die Erwähnung der Wasser- und Abwasser- als Nebenkosten in der Vertragsänderung die Wiederholung einer früheren Abmachung darstellte, schliesst dies notwendig die Feststellung ein, der Beschwerdeführer sei sich tatsächlich bereits bei Vertragsschluss der betreffenden Nebenkostenausscheidung bewusst gewesen. Auch insoweit ist die Beschwerde zum Scheitern verurteilt.
4. Aus den dargelegten Gründen ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Verfahrensausgang wird der Beschwerdeführer für das bundesgerichtliche Verfahren kosten- und entschädigungspflichtig.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgekosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3. Der Beschwerdeführer hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 5. März 2012
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Luczak