2. Streitig und zu prüfen ist der Zeitpunkt, ab welchem die Unfallversicherung eine Hilflosenentschädigung auszurichten hat. Hingegen ist nicht mehr umstritten, dass nur Anspruch auf eine Entschädigung für eine Hilflosigkeit leichten Grades besteht. Ebenso unbestritten sind die ab 1. Juni 2002 laufende Invalidenrente und die Integritätsentschädigung.

2.1 Die Schweizerische Unfallversicherungsanstalt (SUVA) sprach die Hilflosenentschädigung ab 1. Januar 2000 zu, während die Vorinstanz den Beginn im Sinne einer reformatio in peius auf den 1. August 2001 festsetzte. Der Versicherte verlangt die Hilflosenentschädigung wie vor der Vorinstanz ab 1. Mai 1998.

2.2 Der Beschwerdeführer begründet seinen Anspruch damit, dass er am 24. April 1998 aus dem Paraplegikerzentrum X. ausgetreten sei. Sein Gesundheitszustand sei im damaligen Zeitpunkt stabilisiert gewesen. Wohl bestimme Art. 37 Abs. 1 UVV, dass der Anspruch auf eine Hilflosenentschädigung am ersten Tag des Monats beginne, in dem die Voraussetzungen erfüllt seien, frühestens jedoch beim Beginn eines allfälligen Rentenanspruchs. Im vorliegenden Fall seien die beruflichen Eingliederungsmassnahmen der Invalidenversicherung im Sommer 2001 abgeschlossen worden, weshalb er an sich erst ab dem 1. August 2001 den Anspruch auf eine Rente der Unfallversicherung erheben könne. Insofern stehe der Entscheid der Vorinstanz, die Hilflosenentschädigung ebenfalls erst ab 1. August 2001 laufen zu lassen, im Einklang mit Art. 37 UVV. Indessen sei diese Verordnungsbestimmung gesetzwidrig und stehe namentlich in Widerspruch zu Art. 26 UVG. Dort würden die Voraussetzungen für eine Hilflosenentschädigung umschrieben, wobei sich kein Zusammenhang zum Rentenanspruch herauslesen lasse. Eine solche Verknüpfung sei auch überflüssig, da der Renten- und der Hilflosenentschädigungsanspruch an unterschiedliche Voraussetzungen gebunden seien. Art. 37 UVV führe vielmehr zu nicht haltbaren Ergebnissen: so könnten Versicherte, die beruflich gut eingegliedert seien und deshalb keinen Rentenanspruch hätten, gar keine Hilflosenentschädigung beziehen, auch wenn sie hilflos seien.

2.3 Die Vorinstanz erwog hiegegen, Art. 37 UVV sei gesetzeskonform. Solange kein Anspruch auf eine Hilflosenentschädigung der Unfallversicherung bestehe, habe stattdessen die Invalidenversicherung eine solche Leistung zu erbringen. Das Eidgenössische Versicherungsgericht habe dies in BGE 124 V 166 auch für den Fall bestätigt, dass die Hilflosigkeit ausschliesslich auf einen Unfall zurückzuführen sei. Ein gleichzeitiger Bezug beider Hilflosenentschädigungen sei sodann ausgeschlossen. Demnach sei Art. 37 UVV, auch wenn dies im genannten Urteil nicht ausdrücklich gesagt werde, als gesetzeskonform zu betrachten. Auch die SUVA hat in der Duplik an die Vorinstanz darauf hingewiesen, dass Art. 37 UVV die Ansprüche auf die Hilflosenentschädigung der Invalidenversicherung einerseits und der Unfallversicherung anderseits voneinander abgrenze und die Invalidenversicherung prioritär zu leisten habe.

3. Angesichts der geschilderten Argumentationen ist zu prüfen, ob Art. 37 UVV gesetzmässig ist.

3.1 Nach der Rechtsprechung kann das Eidgenössische Versicherungsgericht Verordnungen des Bundesrates grundsätzlich, von hier nicht in Betracht fallenden Ausnahmen abgesehen, auf ihre Rechtmässigkeit hin überprüfen. Bei unselbstständigen Verordnungen, die sich auf eine gesetzliche Delegation stützen, geht es in erster Linie darum zu beurteilen, ob sie sich im Rahmen der Delegationsnorm halten. Besteht ein sehr weiter Spielraum des Ermessens für die Regelung auf Verordnungsebene, muss sich das Gericht auf die Prüfung beschränken, ob die umstrittenen Vorschriften offensichtlich aus dem Rahmen der im Gesetz delegierten Kompetenzen herausfallen oder aus anderen Gründen verfassungs- oder gesetzwidrig sind (vgl. Art. 191 BV). Es kann sein eigenes Ermessen nicht an die Stelle desjenigen des Bundesrates setzen, und es hat auch nicht die Zweckmässigkeit zu untersuchen (BGE 131 V 14 E. 3.4.1; BGE 131 II 566 E. 3.2, BGE 129 V 740 E. 4.1). Die vom Bundesrat verordnete Regelung verstösst allerdings dann gegen das Willkürverbot oder das Gebot der rechtsgleichen Behandlung (Art. 9 und 8 Abs. 1 BV), wenn sie sich nicht auf ernsthafte Gründe stützen lässt, wenn sie sinn- oder zwecklos ist oder wenn sie rechtliche Unterscheidungen trifft, für die sich ein vernünftiger Grund nicht finden lässt. Gleiches gilt, wenn die Verordnung es unterlässt, Unterscheidungen zu treffen, die richtigerweise hätten berücksichtigt werden sollen (BGE 131 II 166 E. 2.3, BGE 129 V 275 E. 4; BGE 131 V 266 E. 5.1; BGE 130 V 473 E. 6.1; BGE 130 I 32 E. 2.2.1; BGE 129 II 164 E. 2.3; BGE 129 V 271 E. 4.1.1, BGE 129 V 329 E. 4.1, je mit Hinweisen; vgl. auch BGE 130 V 45 E. 4.3).

3.2 Sowohl Art. 26 UVG, welcher den Anspruch auf eine Hilflosenentschädigung als solchen regelt, als auch Art. 27 UVG, welcher sich zu deren Höhe äussert, sagen nichts aus zum Beginn des Anspruchs auf die genannte Leistung.

3.3 Art. 37 Satz 1 UVV bestimmt, das der Anspruch auf eine Hilflosenentschädigung am ersten Tag des Monats entsteht, in dem die Voraussetzungen erfüllt sind, jedoch frühestens beim Beginn eines allfälligen Rentenanspruchs. Mit diesem Wortlaut, der insoweit mit der französischen und der italienischen Fassung von Art. 37 UVV übereinstimmt, stellt die genannte Vorschrift einen Zusammenhang her zwischen der Hilflosenentschädigung und der Rente. Es fragt sich, ob sich dafür ein vernünftiger Grund finden lässt.

3.4 Zunächst fällt auf, dass die Invalidenversicherung und die Militärversicherung keinen solchen Zusammenhang kennen (vgl. Art. 35 Abs. 1 IVV und Art. 20 MVG). Dies macht denn auch Sinn, weil die bei der Hilflosenentschädigung verlangte Hilflosigkeit und die bei der Rente vorausgesetzte Invalidität zwei verschiedene Begriffe sind (so schon ZAK 1970 S. 478 E. 1c; vgl. auch ZAK 1971 S. 78 E. 3b, Urteile vom 13. Oktober 2005 E. 4.3 [I 431/05] und vom 4. Februar 2004 E. 3.2 [H 128/03], je mit Hinweisen). Sie haben nur so viel gemeinsam, als beide an eine Beeinträchtigung der Gesundheit anknüpfen (vgl. Art. 7 und 8 ATSG einerseits mit Art. 9 ATSG anderseits). Wohl sprechen Art. 26 Abs. 1 UVG und Art. 42 Abs. 2 IVG (je in den bis Ende 2002 gültig gewesenen Fassungen) von "Invalidität". Dies ändert jedoch nichts daran, dass der Begriff der Hilflosigkeit schon vor dem Inkrafttreten des ATSG am 1. Januar 2003 nicht an die Invalidität im Sinne des Gesetzes (d.h. an die Erwerbsunfähigkeit gemäss alt Art. 4 Abs. 1 IVG) angeknüpft hat. In SVR 2005 IV Nr. 4 S. 14 (Urteil vom 2. Juni 2004, I 127/04) hielt das Eidgenössische Versicherungsgericht fest, dass der Gesetzgeber in Art. 9 ATSG die bisherige Definition der Hilflosigkeit übernehmen wollte (vgl. BBl 1991 II 249). Die Bestimmung weicht von der bisherigen Umschreibung in alt Art. 42 Abs. 2 IVG allerdings dahingehend ab, dass anstelle der "Invalidität" von einer "Beeinträchtigung der Gesundheit" ausgegangen wird, was einerseits eine gewisse Ausweitung darstellt (KIESER, ATSG-Kommentar N. 3 zu Art. 9). Andererseits drückt der Wortlaut der Bestimmung nur aus, was schon nach altem Recht gegolten hatte. Der Terminus "Invalidität" in alt Art. 42 Abs. 2 IVG wollte die Anspruchsberechtigung für eine Hilflosenentschädigung nicht auf Invalide im Sinne von alt Art. 4 IVG, das heisst auf Versicherte, die infolge eines geistigen oder körperlichen Gesundheitsschadens in ihrer Erwerbsfähigkeit beeinträchtigt waren, beschränken. Vielmehr hatte das Wort "Invalidität" dort nicht eine wirtschaftliche Bedeutung, sondern diejenige der körperlichen und oder geistigen Behinderung. Gerade körperlich Behinderte - exemplarisch sei an Rollstuhlfahrer erinnert -, die dank einer guten Eingliederung wegen ihres Gesundheitsschadens keine Erwerbseinbusse erleiden, hingegen in den alltäglichen Lebensverrichtungen dauernd auf die Hilfe Dritter angewiesen sind, waren schon bisher anspruchsberechtigt. Das ATSG hat demnach mit der neuen Formulierung von Art. 9 insbesondere einen redaktionellen Fehler eliminiert (SVR 2005 IV Nr. 4 S. 15 E. 2.2.1 in fine).

3.5 Dass Hilflosigkeit und Invalidität zwei verschiedene Dinge sind, zeigt sich nicht nur darin, dass viele Versicherte, insbesondere Paraplegiker, zwar eine Hilflosenentschädigung beziehen, dank einer guten beruflichen Eingliederung aber keinen Rentenanspruch haben (neben dem in SVR 2005 IV Nr. 4 S. 14 publizierten Urteil vgl. etwa BGE 117 V 146). Umgekehrt gibt es auch Versicherte, die vollständig invalid sind und daher eine ganze Rente beziehen, ihre alltäglichen Lebensverrichtungen jedoch selber besorgen können und deshalb nicht hilflos sind. Insoweit ist kein vernünftiger Grund für den in Art. 37 UVV bezüglich des Beginns des Anspruchs auf eine Hilflosenentschädigung vorgenommenen Zusammenhangs mit der Rente zu erkennen.

3.6 Der Konnex zwischen der Hilflosenentschädigung und der Rente in Art. 37 UVV mag seinen Grund im Verständnis des früheren Unfallversicherungsrechts haben. Damals war die Hilflosigkeit nicht in der Form einer eigenständigen Leistung abgegolten worden, sondern als (lohnabhängiger) Zuschlag zur Invalidenrente (Art. 77 Abs. 1 KUVG; MAURER, Recht und Praxis der schweizerischen obligatorischen Unfallversicherung, 2. Aufl., 1963, S. 242). Wohl aus dieser Optik heraus hat das Bundesamt für Sozialversicherungen (BSV) im Vorentwurf für die UVV vom 20. März 1980 einen Text vorgeschlagen, der im Wesentlichen mit dem heutigen Art. 37 Satz 1 UVV übereinstimmt (Art. 34 Abs. 1 UVV-Entwurf). Dem hat die Kommission zur Vorbereitung der Verordnung über die obligatorische Unfallversicherung am 13./14. August 1980 diskussionslos zugestimmt (Protokoll S. 15; vgl. auch Protokoll der Sitzungen vom 29./30. April und 5. Mai 1981 S. 56). Im zweiten Entwurf des BSV vom Februar 1982 ist - nebst der Streichung eines Wortes im Nebensatz - zum Wort "Rentenanspruch" das "allfällig" eingefügt worden; dies wohl aus der Überlegung heraus, dass es eben auch Fälle von hilflosen Versicherten gibt, denen dank einer erfolgreichen Eingliederung gar kein Rentenanspruch zusteht. Bei dieser Formulierung blieb es im dritten und vierten Entwurf. Schliesslich hat die Kommission den so bereinigten Art. 37 UVV am 29./30. März 1982 ohne Diskussion angenommen (Protokoll S. 25). Den Materialien zur UVV lässt sich somit nicht entnehmen, weshalb im Falle der Berentung die Hilflosenentschädigung erst ab dem Zeitpunkt des Rentenbeginns laufen soll und nicht schon dann, wenn die Voraussetzungen für die Entschädigung erfüllt sind.

3.7 Falls Art. 37 UVV durch das altrechtliche Verständnis der Abgeltung von Hilflosigkeit im Rahmen der Berentung beeinflusst worden sein sollte, müsste jedoch insofern ein Widerspruch festgestellt werden, als in der Botschaft zum UVG ausdrücklich gesagt wird, dass die Hilflosenentschädigung nicht wie bisher als lohnabhängiger Rentenzuschlag, sondern wie in der Invalidenversicherung als eigenständige Leistung gewährt werden soll (BBl 1976 III 169), und dass die Voraussetzungen für den Anspruch auf eine Hilflosenentschädigung der Unfallversicherung dieselben sein sollen wie in der Invalidenversicherung (BBl 1976 III 193). Mit andern Worten lag der Botschaft die Überlegung zu Grunde, die Hilflosenentschädigung von der Rente abzukoppeln. Auch dies spricht dafür, dass sich der in Art. 37 UVV verankerte Konnex zwischen der Hilflosenentschädigung und der Rente nicht auf ernsthafte Gründe stützen lässt.

3.8 Die Vorinstanz stellt zur Bejahung der Gesetzmässigkeit von Art. 37 UVV auf BGE 124 V 166 ab. In diesem Urteil ging es indessen einzig um die Koordination bzw. Kumulation der Hilflosenentschädigung der Unfallversicherung einerseits mit derjenigen der Invalidenversicherung (und der Alters- und Hinterlassenenversicherung) anderseits. Wohl wird Art. 37 UVV in Verbindung mit Art. 19 UVG in einer Klammer zitiert (BGE 124 V 170 f. E. 4b); indessen hat sich für das Eidgenössische Versicherungsgericht die Frage der Verfassungs- und Gesetzmässigkeit von Art. 37 UVV in diesem Fall gar nicht gestellt, weshalb sie denn auch weder aufgeworfen noch geprüft wurde. Das räumt auch die Vorinstanz ein. Damit geht deren Berufung auf das genannte Urteil fehl.

3.9 Schliesslich spricht auch die folgende Überlegung gegen ernsthafte Gründe für die in Art. 37 UVV statuierte Verknüpfung von Hilflosenentschädigung und Rente:

Gemäss Art. 19 Abs. 1 UVG entsteht der Rentenanspruch, wenn (1) von der Fortsetzung der ärztlichen Behandlung keine namhafte Besserung des Gesundheitszustandes mehr erwartet werden kann und (2) allfällige Eingliederungsmassnahmen der Invalidenversicherung abgeschlossen sind. Der zweite Sachverhalt (Abschluss der Eingliederung durch die Invalidenversicherung) hat keinen Zusammenhang mit der Frage der Hilflosigkeit. Muss eine versicherte Person trotz einer an sich bereits bestehenden Hilflosigkeit im Sinne von Art. 38 Abs. 2 bis 4 UVV auf den Beginn der Hilflosenentschädigung der Unfallversicherung nur deshalb warten, weil die Invalidenversicherung eine berufliche Eingliederung durchführt und darum noch kein Anspruch auf eine Rente der Unfallversicherung entstehen kann, wird hier mit Bezug auf den Beginn der Hilflosenentschädigung ein Umstand berücksichtigt, der mit der Hilflosigkeit nichts zu tun hat. Dies gilt an sich auch für den ersten Sachverhalt (Abschluss der Heilbehandlung). Denn auch der Zeitpunkt des Abschlusses hat keinen Einfluss darauf, ob Hilflosigkeit besteht oder nicht. Ein Vorbehalt ist jedoch für den Fall anzubringen, dass die Heilbehandlung in einem Spital durchgeführt wird. Dass hier eine allfällige Hilflosigkeit nicht durch eine Hilflosenentschädigung abgegolten wird, ist gesetzlich geregelt (vgl. den Ende 2002 aufgehobenen Art. 26 Abs. 2 UVG; seit dem 1. Januar 2003 ist dieser Sachverhalt in Art. 67 Abs. 2 ATSG festgehalten). Wenn Art. 26 Abs. 1 UVG klar und unzweideutig festhält, dass der Versicherte bei Hilflosigkeit (Art. 9 ATSG) Anspruch auf eine Hilflosenentschädigung hat, verletzt Art. 37 UVV diesen gesetzlichen Grundsatz insoweit, als ein Anspruch auf Hilflosenentschädigung "frühestens beim Beginn eines allfälligen Rentenanspruchs" eingeräumt wird. Dieser Vorbehalt erweist sich nach dem Gesagten als gesetzwidrig.