Sachverhalt:
A. Am 28. November 2004 fand in der Stadt Bern die im Proporzverfahren durchgeführte Wahl des Gemeinderates (Exekutive) für die Amtsdauer 2005 - 2008 statt. Gemäss Protokoll der Stadtkanzlei erzielte die RotGrünMitte-Liste aufgrund der Gesamtzahl der Listenstimmen drei Gemeinderatssitze. Auf dieser Liste belegte Regula Rytz mit 20'606 Stimmen den dritten Rang; sie hatte 19 Stimmen mehr erhalten als Alec von Graffenried mit 20'587 Stimmen auf dem vierten Rang. Demnach war Regula Rytz in den Gemeinderat gewählt, während Alec von Graffenried ausschied.
Der Gemeinderat nahm am 1. Dezember 2004 vom Bericht der Stadtkanzlei über die Gemeinderatswahl Kenntnis und wies gleichzeitig das Begehren der Grünen Freien Liste (GFL) um Nachzählung ab. Demnach galt Regula Rytz als in den Gemeinderat gewählt.
B. Sebastian Bentz führte in der Folge Gemeindebeschwerde bei der Regierungsstatthalterin und verlangte eine Nachzählung der Wahlzettel und eine Auswertung einzelner Kategorien von Wahlzetteln. Mit separater Eingabe erhoben Bruno Studer, Martin Kindler und Marcel Studer Wahlbeschwerde und beantragten ebenfalls die Nachzählung der für Regula Rytz bzw. Alec von Graffenried abgegebenen sowie der ungültig erklärten Stimmen.
Die Justiz-, Gemeinde- und Kirchendirektion des Kantons Bern wies am 9. Dezember 2004 ein Ablehnungsbegehren gegen die Regierungsstatthalterin ab.
Die Regierungsstatthalterin entzog der Beschwerde die aufschiebende Wirkung, führte eine Untersuchung und wies die Beschwerden am 10. Januar 2005 ab. Zur Begründung führte sie aus, der Gemeinderat habe das Reglement der Stadt Bern über die politischen Rechte korrekt angewendet, das Vorliegen einer geringen Stimmendifferenz begründe für sich allein keinen Anspruch auf Nachzählung und es lägen - nach Abklärung der Verhältnisse im Zählkreis 5 - keine Hinweise auf Unregelmässigkeiten vor, sodass die Knappheit des Resultates keine Zweifel an der Richtigkeit der Ermittlungen des Wahlergebnisses zu begründen vermöge.
C. Bruno Studer, Martin Kindler und Marcel Studer fochten diesen Entscheid beim Regierungsrat des Kantons Bern an. Mit separater Eingabe erhob auch Sebastian Bentz Beschwerde. Sie machten im Wesentlichen geltend, in Anbetracht notorischer Zählfehler bestehe bei knappem Wahlausgang aufgrund von <ref-law> ein Anspruch auf Nachzählung. Im Übrigen bemängelten sie das Verfahren der Auszählung und rügten teilweise Verletzungen des rechtlichen Gehörs.
Das Rechtsamt der Justiz-, Gemeinde- und Kirchendirektion entzog der Beschwerde am 9. Februar 2005 die aufschiebende Wirkung und nahm verschiedene Instruktionsmassnahmen vor. Mit Entscheid vom 20. April 2005 wies der Regierungsrat die Beschwerden ab. Er hielt fest, dass ein knappes Resultat für sich allein genommen keinen Anspruch auf eine Nachzählung begründe. Gewisse - ausdrücklich festgehaltene - Mängel des Auszählungsverfahrens hätten sich auf das Wahlresultat und insbesondere auf den Stimmenunterschied zwischen Regula Rytz und Alec von Graffenried nicht ausgewirkt.
D. Gegen diesen Entscheid des Regierungsrates haben Bruno Studer, Martin Kindler und Marcel Studer beim Bundesgericht am 20. Mai 2005 staatsrechtliche Beschwerde wegen Verletzung von <ref-law> erhoben. Sie machen im Wesentlichen geltend, angesichts des knappen Wahlresultats und konkreter Anhaltspunkte für fehlerhafte bzw. gesetzwidrige Auszählung einen Anspruch auf Nachzählung zu haben.
Der Gemeinderat stellt mit seiner Vernehmlassung den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Justiz-, Gemeinde- und Kirchendirektion beantragt für den Regierungsrat die Abweisung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
1. Die Beschwerdeführer erheben mit ihrer staatsrechtlichen Beschwerde wegen Verletzung von <ref-law> Stimmrechtsbeschwerde gemäss Art. 85 lit. a OG. Diese kann sich gegen eine kommunale Stimmrechtssache richten (vgl. <ref-ruling> E. 11.1 S. 188). Hierzu sind die Beschwerdeführer als Stimmbürger der Stadt Bern legitimiert (vgl. <ref-ruling> E. 1.2 S. 292). Wegen der den Stimmberechtigten zukommenden Organfunktion (vgl. <ref-ruling> E. 1d S. 171 f.) brauchen sie hierfür kein besonderes persönliches Interesse an der Beschwerdeführung auszuweisen (vgl. <ref-ruling> E. 1.1 S. 193). Demnach kann auf die vorliegende Beschwerde eingetreten werden.
Bei Stimmrechtsbeschwerden prüft das Bundesgericht nicht nur die Auslegung und Anwendung von eidgenössischem und kantonalem Verfassungsrecht frei, sondern auch von kantonalen und kommunalen Vorschriften, welche den Inhalt der politischen Rechte umschreiben oder mit diesem in engem Zusammenhang stehen (vgl. <ref-ruling> E. 2 S. 190, 123 I 175 E. 2d/aa S. 178).
2. Der Regierungsrat hat im angefochtenen Entscheid in verschiedener Hinsicht Unregelmässigkeiten im Zusammenhang mit der Auszählung der Wahlzettel festgehalten. Er kam indessen zum Schluss, dass diese durch eine Nachzählung nicht behoben werden könnten, und fügte an, dass sie sich auf das umstrittene Wahlresultat nicht ausgewirkt hätten. Zusammenfassend hielt er fest, dass für die Stadt Bern im Sinne einer Anpassung der Praxis an die Rechtsgrundlagen Handlungsbedarf bestehe.
2.1 Gemäss der in der Stadt Bern gehandhabten Praxis sind anlässlich der Gemeinderatswahl die unveränderten Wahlzettel aus der brieflichen Stimmabgabe nicht mit amtlicher Kennzeichnung (durch Stempelung oder Stanzung) versehen worden. Demgegenüber sind die veränderten Wahlzettel aus der brieflichen Stimmabgabe gestanzt worden.
Die briefliche Stimmabgabe wird nach Art. 8 des städtischen Reglements über die politischen Rechte (RPR; SSSB 141.1) unter den gleichen Voraussetzungen und im gleichen Verfahren gestattet wie für kantonale Abstimmungen und Wahlen. Art. 28 Abs. 3 der Verordnung des Regierungsrates des Kantons Bern über die politischen Rechte (VPR/BE; BSG 141.112) schreibt vor, dass die in den Antwortcouverts enthaltenen Wahlzettel abgestempelt und in die Urne gelegt werden. In Art. 28 Abs. 5 VPR/BE wird vorgesehen, dass der Regierungsstatthalter Gemeinden mit über 5'000 Stimmberechtigten ermächtigen kann, an Stelle der Stempelung ein gleichwertiges maschinelles Verfahren der amtlichen Kennzeichnung zu verwenden; dazu gehört insbesondere die Stanzung. Schliesslich hält Art. 43 Abs. 1 lit. b RPR fest, dass Wahlzettel ungültig sind, wenn sie nicht abgestempelt oder gestanzt sind.
2.2 Der Regierungsrat hielt in diesem Zusammenhang vorerst fest, dass das Fehlen einer Stempelung oder Stanzung auf den unveränderten Wahlzetteln aus brieflicher Stimmabgabe sehr aussergewöhnlich sei und gegen eine grundlegende Bestimmung des städtischen Reglements über die politischen Rechte verstosse. Diese Regelwidrigkeit lasse sich indessen durch die von den Beschwerdeführern geforderte Nachzählung nicht beseitigen. Entscheidend im vorliegenden Fall sei vielmehr, dass sich die Regelwidrigkeit nicht auf das Wahlergebnis von Regula Rytz und Alec von Graffenried bzw. auf die sie trennende Stimmendifferenz ausgewirkt habe. Denn beide hatten auf derselben RotGrünMitte-Liste kandidiert, sodass die gleiche - wenn auch regelwidrige - Behandlung der unveränderten Listen zu keiner Verfälschung des Wahlergebnisses geführt habe.
Weiter legte der Regierungsrat dar, dass die unterschiedliche Behandlung der veränderten Wahlzettel einerseits, welche gestanzt wurden, und der unveränderten Wahlzettel andererseits, welche nicht gestanzt wurden, sich auf das Wahlergebnis ebenfalls nicht ausgewirkt habe. Bei der Verarbeitung der brieflichen Stimmabgabe werden die Wahlzettel nach unveränderten, veränderten, leeren und ungültigen sortiert. Insbesondere werden die veränderten und die unveränderten Wahlzettel getrennt voneinander gezählt bzw. gewogen. Demnach vermöge die Stanzung bzw. Nichtstanzung keine Gewichtsveränderung und demnach keine Verfälschung des Wahlergebnisses zu bewirken.
Festgehalten wurde ferner, dass es an der nach Art. 28 Abs. 5 VPR/BE erforderlichen Bewilligung fehle, anstelle einer Stempelung der brieflich abgegebenen Wahlzettel eine Stanzung vorzunehmen. Auch insofern vermöge eine Nachzählung den Mangel nicht zu beheben. Entscheidend sei gesamthaft betrachtet, dass mit der Stanzung eines Kreuzes das Erfordernis einer amtlichen Kennzeichnung klar erfüllt sei. Auch in dieser Hinsicht sei ein Einfluss auf das Wahlergebnis nicht ersichtlich.
Schliesslich legte der Regierungsrat unter Hinweis auf die Anleitung für die Ausmittlung der Gemeinderats- und Stadtratswahlen und die getroffenen Abklärungen im Einzelnen dar, dass das Verfahren der Auszählung der brieflich eingereichten Wahlzettel Gewähr für eine korrekte Ermittlung des Wahlergebnisses biete. Die unveränderten Wahlzettel werden nach Listen sortiert und die Bündel nochmals daraufhin kontrolliert, dass sich nur unveränderte Listen darin befinden. Diese Bündel werden zwei Mal gewogen und schliesslich listenweise verpackt, etikettiert, mit den Angaben über Wahl, Zählkreis, Liste und brieflicher Stimmabgabe versehen und anschliessend plombiert. Gesamthaft wird demnach die Ermittlung der brieflich eingelegten Wahlzettel zentralisiert und unter doppelter Kontrolle jedes Ausmittlungsschrittes durchgeführt.
2.3 Die Beschwerdeführer stellen diese Ausführungen nicht grundsätzlich in Frage. Insbesondere machen sie nicht geltend, dass sich das Fehlen einer amtlichen Kennzeichnung der brieflich eingelegten unveränderten Wahlzettel auf das Wahlergebnis hätte auswirken können. Ebenso wenig wird ausgeführt, die fehlende Bewilligung für die Stanzung der Wahlzettel (anstelle der Stempelung) hätte einen Einfluss auf das Resultat haben können. Schliesslich bringen sie auch nicht vor, dass das Auszählverfahren, wie es in den verschiedenen Bestimmungen allgemein geordnet und in der Anleitung für die Ausmittlung der Gemeinderats- und Stadtratswahlen im Speziellen umschrieben ist, im Grundsatz nicht hinreichend Gewähr für eine korrekte Ermittlung der Wahlresultate zu bieten vermöge.
3. Die Beschwerdeführer machen zur Hauptsache geltend, in Anbetracht des knappen Wahlresultats (von 19 Stimmen Unterschied zwischen Regula Rytz und Alec von Graffenried bei rund 20'000 Kandidatenstimmen) sowie tatsächlicher Unregelmässigkeiten und stets möglicher Fehler bei der Ermittlung des Wahlresultats hätten sie aufgrund von <ref-law> einen Anspruch auf Überprüfung des Resultats und Nachzählung der Wahlzettel. Der Regierungsrat hat einen solchen Anspruch in Übereinstimmung mit dem Gemeinderat im vorliegenden Fall verneint.
3.1 <ref-law> gewährleistet die politischen Rechte (auf Bundes- sowie Kantons- und Gemeindeebene) in abstrakter Weise und ordnet die wesentlichen Grundsätze der demokratischen Partizipation im Allgemeinen. Der konkrete Gehalt der politischen Rechte mit ihren mannigfaltigen Teilgehalten ergibt sich indessen in erster Linie aus dem spezifischen Organisationsrecht des Bundes bzw. der Kantone. Die Kantone ordnen gemäss <ref-law> die politischen Rechte für sich und die Gemeinden nach Massgabe von <ref-law> in ihren Verfassungen und gesetzlichen Bestimmungen; im Rahmen der kantonalen Gesetzgebung kommt den Gemeinden eine entsprechende Regelungskompetenz zu (vgl. Gerold Steinmann, Die Gewährleistung der politischen Rechte durch die neue Bundesverfassung [Artikel 34 BV], in: ZBJV 139/2003 S. 485). Darüber hinaus schützt <ref-law> in Übereinstimmung mit der bereits unter der alten Bundesverfassung anerkannten Stimm- und Wahlfreiheit (vgl. <ref-ruling> E. 3 S. 141) die freie Willensbildung und unverfälschte Stimmabgabe. Sie bedeutet, dass kein Abstimmungs- oder Wahlergebnis anerkannt wird, das nicht den freien Willen der Stimmbürger zuverlässig und unverfälscht zum Ausdruck bringt. Dazu gehört u.a., dass Wahl- und Abstimmungsergebnisse sorgfältig und ordnungsgemäss ermittelt werden (<ref-ruling> E. 4 S. 85, 104 Ia 428 E. 3a S. 431, 121 I 138 E. 3 S. 142, mit Hinweisen), gegen Wahl- und Abstimmungsergebnisse vorgebrachte Rügen - mit der allfälligen Folge einer Nachzählung oder Aufhebung des Urnengangs - im Rahmen des einschlägigen Verfahrensrechts geprüft werden (<ref-ruling>) und ordnungsgemäss zustande gekommene Wahl- oder Abstimmungsergebnisse tatsächlich anerkannt werden (<ref-ruling> E. 1b S. 211).
3.2 Es ist in erster Linie eine Frage des kantonalen Rechts, unter welchen Voraussetzungen Nachzählungen von Wahl- und Abstimmungsergebnissen anzuordnen sind und ob der einzelne Stimmberechtigte eine Nachzählung erwirken kann (vgl. <ref-ruling> E. 4 S. 84, 114 Ia 42). Im vorliegenden Fall hat der Regierungsrat (wie vorher bereits die Regierungstatthalterin) die Vorbringen der Beschwerdeführer hinsichtlich der Unregelmässigkeiten der Ermittlung des Wahlresultats tatsächlich und eingehend geprüft, indessen einen Anspruch der Beschwerdeführer auf Nachzählung aufgrund des anzuwendenden städtischen Reglements über die politischen Rechte verneint. Dieses enthält folgende Bestimmung:
Art. 25 - Nachzählung
Bestehen Zweifel an der Richtigkeit der ermittelten Resultate, so kann der Gemeinderat eine Nachzählung veranlassen.
Nach der bundesgerichtlichen Rechtsprechung kann die zuständige Behörde auch ohne entsprechende gesetzliche Bestimmung von Amtes wegen eine Nachkontrolle eines Wahl- oder Abstimmungsergebnisses anordnen, falls es nach der gegebenen Sachlage als für die zuverlässige Ermittlung geboten erscheint (<ref-ruling> E. 4a S. 245, 104 Ia 428 E. 3c S. 432, ZBl 78/1977 S. 451 E. 2b, mit Hinweisen). Im Einzelnen mag es dem Gebot politischer Klugheit entsprechen, bei gegebener Sachlage eine Nachzählung vorzunehmen (<ref-ruling> E. 4 S. 85; vgl. ZBl 78/1977 S. 451 [Billigung des Ergebnisses einer Nachzählung]). Eine solche von Amtes wegen angeordnete Nachzählung kann sich umso mehr rechtfertigen, wenn der Aufwand verhältnismässig ist und sich dadurch keine wesentlichen Verzögerungen ergeben (vgl. 1P363/1994 vom 15. Dezember 1994, E. 3d). In diesem Sinne hielt der Regierungsrat fest, dass der Gemeinderat in Ausübung von Art. 25 RPR grundsätzlich von Amtes wegen eine Nachzählung anordnen könne, dass Art. 25 RPR den Stimmberechtigten jedoch keinen Anspruch auf Nachzählung einräume.
Die Beschwerdeführer ziehen diese Auslegung des Reglements über die politischen Rechte nicht in Zweifel und werfen dem Regierungsrat nicht vor, gestützt auf Art. 25 RPR zu Unrecht einen Anspruch auf Nachzählung verneint zu haben. Sie beziehen sich auch sonst wie nicht auf kantonales Recht (vgl. Art. 44 VPR/BE). Einen entsprechenden Anspruch auf Nachzählung leiten sie vielmehr direkt aus <ref-law> ab.
3.3 Vorerst gilt es festzuhalten, dass im demokratischen Entscheidfindungsprozess auch knappe Wahl- und Abstimmungsergebnisse tatsächlich anzuerkennen sind und nicht wegen kleiner Stimmenunterschiede in Frage gestellt werden sollen (vgl. <ref-ruling> E. 1b S. 211, 104 Ia 428 E. 3b S. 431 f., ZBl 65/1964 S. 22). Grundlage hierfür ist indessen, dass Wahl- und Abstimmungsergebnisse ordnungsgemäss zustande kommen und Wahl- und Abstimmungszettel korrekt und regelkonform ausgezählt werden.
Nach der bundesgerichtlichen Rechtsprechung besteht - unter der Voraussetzung einer zweckmässigen kantonalen Ordnung, welche Gewähr für eine sorgfältige Ermittlung der Wahl- und Abstimmungsergebnisse bietet - eine sich aus dem Bundes(verfassungs)recht ergebende Verpflichtung zur Nachzählung bloss in jenen knapp ausgegangenen Fällen, in denen der Bürger auf konkrete Anhaltspunkte für eine fehlerhafte Auszählung oder für ein gesetzwidriges Verhalten der zuständigen Organe hinzuweisen vermag. Der blosse Umstand eines knappen Wahl- oder Abstimmungsergebnisses begründet für sich allein genommen keine Pflicht zur Nachzählung (<ref-ruling> E. 4 S. 85, vgl. auch 114 Ia 42 E. 4c S. 46). An dieser Rechtsprechung hat das Bundesgericht seither festgehalten. In einem neuesten Entscheid wurde ein Anspruch auf Nachzählung bei Vorliegen eines knappen Wahlresultats mangels konkreter Hinweise auf fehlerhafte Auszählung oder gesetzwidriges Verhalten unter Hinweis auf das Verfahren der Ermittlung der Ergebnisse verneint (1P.369/2004 vom 13. Juni 2005).
Schliesslich geht auch ein Entscheid des Bundesgerichts aus dem Jahre 1994 von diesen Grundlagen aus (1P.363/1994 vom 15. Dezember 1994). Er betraf das äusserst knappe Wahlresultat im Wahlkreis La Sarraz (VD) zu einer waadtländischen Grossratswahl, in der eine Partei in einer Proporzwahl einen Sitz lediglich um zwei Stimmen verpasste. Die gegen die Verweigerung einer Nachzählung erhobene staatsrechtliche Beschwerde wurde indes nicht allein wegen des sehr knappen Wahlausgangs gutgeheissen. Entscheidend war vielmehr, dass gegenüber den Rekurrenten an die nach kantonalem Recht erforderliche Glaubhaftmachung von Unregelmässigkeiten - in Anbetracht des Umstandes, dass das Resultat sehr knapp war und ein isolierter Auszählfehler von bereits zwei Wahlzetteln oder die Gültigkeitsbeurteilung von zwei Wahlzetteln ausschlaggebend sein konnte - allzu strenge Anforderungen gestellt worden waren.
Von der Nachzählung im eigentlichen Sinne ist schliesslich die Wiederholung von Abstimmungen anlässlich von Landsgemeinden und Gemeindeversammlungen zu unterscheiden (vgl. <ref-ruling>, 104 Ia 428). Dabei geht es nicht um die Nachprüfung eines an sich feststehenden Abstimmungsergebnisses, sondern vielmehr um eine Wiederholung einer Abstimmung, die angesichts unterschiedlichen Abstimmungsverhaltens anders ausfallen kann. Von der Frage der Nachzählung ist ferner die Aufhebung von Urnengängen bei festgestellten Unregelmässigkeiten zu trennen. Nach der bundesgerichtlichen Rechtsprechung werden Wahl- und Abstimmungsergebnisse lediglich aufgehoben, wenn die gerügten Unregelmässigkeiten erheblich sind und das Ergebnis beeinflusst haben könnten (vgl. <ref-ruling> E. 8 S. 204, 121 I 1 E. 5b S. 12, ZBl 102/2001 S. 188 E. 4).
3.4 Der Regierungsrat wies im angefochtenen Entscheid darauf hin, dass die Rechtsprechung in andern Kantonen - vorbehältlich spezifischer Rechtsgrundlagen - nach wie vor davon ausgehe, dass der blosse Umstand knapper Ergebnisse keinen Anspruch auf Nachzählung einräumt (vgl. auch die Hinweise bei Bernhard Maag, Urnenwahl von Behörden im Majorzsystem, Diss. Zürich 2004, S. 67 Anm. 155). Diese Praxis verfolgt, soweit ersichtlich, auch der Nationalrat bei Nationalratswahlen (vgl. AB 1975 N 1538 - 1540 betreffend den Kanton Aargau). Gleich verhalte es sich mit den rechtlichen Grundlagen in andern Kantonen. Dem kann angefügt werden, dass zwar eine Reihe von Kantonen eine Nachzählung bei knappem Ausgang vorschreibt (vgl. etwa § 75 Abs. 3 des Gesetzes über die politischen Rechte des Kantons Zürich; Art. 45 der Vollziehungsverordnung des Kantons Obwalden zum Gesetz über die Ausübung der politischen Rechte; Art. 39 Abs. 4 des Urnenabstimmungsgesetzes des Kantons St. Gallen); umgekehrt kennen andere Kantone Bestimmungen, wonach lediglich nachzuzählen ist, wenn stichhaltige Gründe und Zweifel am Ergebnis dies erfordern (vgl. Art. 44 Abs. 2 VPR/BE; § 79 des Gesetzes über Wahlen und Abstimmungen des Kantons Basel-Stadt; § 14 des Gesetzes über die politischen Rechte des Kantons Basel-Landschaft; § 34 der Verordnung über die Wahl des Grossen Rates des Kantons Schaffhausen); nach Art. 11 der eidgenössischen Verordnung über die politischen Rechte (VPR; SR 161.11) zählt das kantonale Wahlbüro bei Nationalratswahlen entweder selber nach oder ordnet eine Nachzählung durch das Gemeindewahlbüro an, wenn Verdacht besteht, dass ein Gemeindeergebnis unrichtig ist.
3.5 Die neuere Doktrin verlangt im Sinne der bundesgerichtlichen Rechtsprechung eine Nachzählung beim Vorliegen von Anzeichen von Unregelmässigkeiten und knappen Ergebnissen und folgert aus dem genannten Entscheid aus dem Jahre 1994, dass bei sehr knappen Ergebnissen auch ohne konkrete Anzeichen von Unregelmässigkeiten nachzuzählen ist (vgl. René Rhinow, Grundzüge des Schweizerischen Verfassungsrechts, Basel 2003, Rz. 1896; Yvo Hangartner/Andreas Kley, Die demokratischen Rechte in Bund und Kantonen der Schweizerischen Eidgenossenschaft, Zürich 2000, Rz. 2561; Jörg P. Müller, Grundrechte in der Schweiz, 3. Aufl. 1999. S. 369; Etienne Grisel, Initiative et référendum populaires, 3. Aufl. 2004, Rz. 292; Pierre Tschannen, Staatsrecht der Schweizerischen Eidgenossenschaft, Bern 2004, § 52 Rz. 69; Piermarco Zen-Ruffinen, L'expression fidèle et sûre de la volonté du corps électoral, in: Thürer/Aubert/Müller (Hrsg.), Verfassungsrecht der Schweiz, Zürich 2001, § 21 Rz. 39). Diese Autoren setzen sich zwar mit der besondern prozessualen Situation des genannten Entscheides nicht näher auseinander. Sie bringen aber im Hinblick auf die erforderliche Glaubwürdigkeit von Wahl- und Abstimmungsresultaten zum Ausdruck, dass Nachzählungen bei sehr knappen Ergebnissen angezeigt seien.
In diesem Sinne äussern sich mit ausführlicherer Begründung insbesondere Stephan Widmer und Bernhard Maag. Ersterer hält dafür, das für jede Demokratie unabdingbare Vertrauen in die Richtigkeit der Ergebnisermittlung und die praktisch nicht vermeidbaren Auszählungsfehler sprächen bei knappen Ergebnissen auch ohne konkrete Anzeichen von Unregelmässigkeiten für einen Anspruch auf Nachzählung (Stephan Widmer, Wahl- und Abstimmungsfreiheit, Diss. Zürich 1989, S. 172 ff.). Letzterer geht davon aus, dass Wahl- und Abstimmungsresultate keine arithmetisch exakte Grösse darstellten. Bei sehr knappen Differenzen dürften nur sehr geringe Anforderungen an die Glaubhaftmachung von Unregelmässigkeiten gestellt werden und könnten einzelne Auszählfehler vermutet werden. Dies führe zur Bejahung eines individuellen Anspruchs auf Nachzählung einzig wegen der Knappheit des Resultats. Im Sinne eines Richtwertes nimmt er dies an, wenn der Abstand der fraglichen Stimmenzahlen weniger als 1 o/oo beträgt (Maag, a.a.O., S. 65 ff.).
3.6 Es darf angenommen werden, dass bei der Ermittlung von Wahl- und Abstimmungsergebnissen, seien sie knapp oder nicht, immer wieder Fehler unterlaufen. Sie können darauf zurückgeführt werden, dass tatsächlich falsch gezählt wird, dass Wahl- und Abstimmungszettel hinsichtlich Gültigkeit oder Ungültigkeit falsch zugeordnet werden (vgl. ZBl 104/2003 S. 584) oder dass einzelne, etwa nicht eindeutig klar geschriebene Namen bei Wahlen unterschiedlich behandelt werden. Die Unsicherheiten mögen bei Abstimmungen mit klarer Ja- bzw. Nein-Antwort kleiner sein als bei Proporzwahlen mit Listen und der Möglichkeit des Kumulierens und Panaschierens (vgl. <ref-ruling> E. 4 S. 86, Urteil 1P.363/1994 vom 15. Dezember 1994, E. 3d). So zeigt sich denn auch, dass Nachzählungen kaum je zu demselben Resultat führen (vgl. <ref-ruling>; ZBl 78/1977 S. 451; zur Abstimmung über die neue Verfassung des Kantons Graubünden die Hinweise bei Maag, a.a.O., S. 65 Anm. 144). Solche Ungenauigkeiten werden in gewissem Ausmass in Kauf genommen, sind bei Landsgemeinden und Gemeindeversammlungen nicht zu vermeiden (vgl. <ref-ruling> E. 3 S. 142, mit Hinweisen) und sollen durch strikte (und einfache) Regeln (vgl. <ref-ruling> E. 3b S.240) sowie durch die Beteiligung von politischen Kräften bei der Auszählung (vgl. Widmer, a.a.O., S. 168; Jörg P. Müller, a.a.O., S. 369 mit Verweis auf Art. 25 UNO-Pakt II) beschränkt werden. Eine gewisse Unsicherheit der Auszählung ist somit dem demokratischen Wahl- und Abstimmungsverfahren inhärent und in gewissen Grenzen hinzunehmen. Eine Grenze der Akzeptanz von Auszählungsunsicherheiten ist indessen erreicht, wenn Unregelmässigkeiten festgestellt werden oder hierfür ernsthafte Anzeichen bestehen und das Wahl- oder Abstimmungsergebnis sehr knapp ausgefallen ist. Diesfalls kann nicht nur ein einzelnes Wahl- oder Abstimmungsergebnis fragwürdig erscheinen, sondern besteht die Gefahr, dass die Glaubwürdigkeit des demokratischen Entscheidungsverfahrens als solches leidet. Es kann dem einzelnen Stimmberechtigten in seiner Organfunktion bei solchen Gegebenheiten nicht verwehrt werden, eine Nachzählung zu verlangen. Dies trifft jedenfalls zu, wenn bei knappem Wahl- oder Abstimmungsergebnis zusätzlich Anzeichen für Unregelmässigkeiten bestehen oder solche gar nachgewiesen sind.
3.7 Vor diesem Hintergrund kommt der kantonal- bzw. kommunalrechtlichen Ordnung des Wahl- und Abstimmungswesens und insbesondere des Auszählverfahrens entscheidende Bedeutung zu (vgl. <ref-ruling> E. 4 S. 85). In dieser Hinsicht führte der Regierungsrat aus, dass die in der Stadt Bern geübte Handhabung grundsätzlich Gewähr für eine korrekte und zuverlässige Ermittlung von Wahl- und Abstimmungsresultaten biete. Er legte dies zwar in erster Linie hinsichtlich der brieflich eingelegten Wahlzettel dar, hielt indessen darüber hinaus allgemein fest, dass aufgrund der rechtlichen Vorgaben sowie der genannten Anleitung für die Ausmittlung der Gemeinderats- und Stadtratswahlen ein durchdachtes System mit mehrfachen Kontrollen bestehe. Die Beschwerdeführer stellen dies mit ihrer Beschwerde nicht in Frage und machen insbesondere nicht geltend, dass das Ermittlungsverfahren systemimmanente Gefahren oder Schwächen aufweise oder sonst wie keine Gewähr für eine korrekte Resultateermittlung biete. Doch weisen sie in allgemeiner Weise darauf hin, dass Auszählungsfehler anerkanntermassen tatsächlich immer vorkommen könnten und das Wahlresultat im vorliegenden Fall daher möglicherweise nicht der tatsächlichen Stimmabgabe entspreche.
Der kantonalen Ordnung des Wahl- und Abstimmungswesens und des Auszählverfahrens ist ferner die kantonale Regelung und Handhabung des Beschwerdeweges zuzuordnen. Der vorliegende Fall zeigt, dass die Beschwerdeführer ihre Rügen vor zwei Instanzen mit voller Rechtskontrolle vorbringen konnten. Sowohl die Regierungsstatthalterin als auch der Regierungsrat haben das in der Stadt Bern gehandhabte Auszählverfahren tatsächlich sehr eingehend geprüft und verschiedene Unregelmässigkeiten klar aufgedeckt (vgl. demgegenüber die Verhältnisse von <ref-ruling>). Insoweit kann festgehalten werden, dass die Beschwerdeführer in den Genuss einer sorgfältigen Prüfung kamen. Daran vermag der Umstand nichts zu ändern, dass der Regierungsrat, wenn auch nicht ausschliesslich, so doch in erster Linie das Verfahren der Auszählung der brieflich eingelegten Wahlzettel untersuchte.
3.8 Bei dieser Sachlage kommt der Glaubhaftmachung von konkreten Anhaltspunkten für Unregelmässigkeiten bzw. der Feststellung von tatsächlichen Unrechtmässigkeiten im Auszählungsverfahren entscheidende Bedeutung zu. Wie dargelegt, können verschiedenste Umstände zu Zählfehlern führen. Solche nachzuweisen, kann dem einzelnen Stimmberechtigten zwar schwer fallen oder sich mangels Einblicks in die Grundlagen gar als unmöglich erweisen (vgl. Urteil 1P.363/1994 vom 15. Dezember 1994, E. 3d). Im vorliegenden Fall haben sich nicht nur Anzeichen für Unregelmässigkeiten gezeigt, sondern sind vom Regierungsrat Unrechtmässigkeiten tatsächlich aufgezeigt sowie als sehr aussergewöhnlich und gegen grundlegende Bestimmungen des Reglements über die politischen Rechte verstossend bezeichnet worden. Damit ist die Glaubwürdigkeit in das festgestellte Wahlergebnis in schwerwiegender Weise erschüttert. Daran vermag der Umstand nichts zu ändern, dass sich die festgestellten Unregelmässigkeiten nach dem angefochtenen Entscheid nicht konkret ausgewirkt haben sollen. Wesentlich ist, dass ein verordnungs- und reglementswidriges Auszählverfahren angewendet worden ist. Ein solches Vorgehen erhöht im Allgemeinen die Gefahr von Auszählungsfehlern. Bei dieser Sachlage kann das für die direkte Demokratie unabdingbare Vertrauen in die Richtigkeit der Ergebnisermittlung der Wahl ohne Nachzählung des knappen Resultats nicht gewahrt werden. Der Anspruch auf Nachzählung geht hier dem Interesse am Festhalten eines einmal ausgezählten und veröffentlichten Wahlergebnisses vor.
In Anbetracht der konkreten Gegebenheiten mit den vom Regierungsrat als gravierend bezeichneten Unregelmässigkeiten im Auszählungsverfahren einerseits und dem äusserst knappen Ausgang zwischen den beiden Kandidaten andererseits können die Beschwerdeführer gestützt auf <ref-law> eine Nachzählung beanspruchen. Daher erweist sich die vorliegende Beschwerde als begründet.
4. Demnach ist die Stimmrechtsbeschwerde gutzuheissen und der angefochtene Entscheid des Regierungsrates aufzuheben. Bei diesem Verfahrensausgang sind keine Kosten zu erheben (Art. 156 OG). Den nicht anwaltlich vertretenen Beschwerdeführern ist keine Parteientschädigung zuzusprechen (vgl. <ref-ruling> E. 5 S. 304, 125 II 518 E. 5b S. 519).

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird gutgeheissen und der Entscheid des Regierungsrates des Kantons Bern vom 20. April 2005 aufgehoben.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Beschwerdeführern, dem Gemeinderat der Stadt Bern, der Regierungsstatthalterin von Bern und dem Regierungsrat des Kantons Bern schriftlich mitgeteilt.
Lausanne, 7. September 2005
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: