Sachverhalt:
A. Mit Schadenersatzverfügung vom 31. Mai 1999 verpflichtete die Ausgleichskasse GastroSuisse R._ zur Bezahlung von Schadenersatz für entgangene Bundessozialversicherungsbeiträge in der Höhe von Fr. 98'465.25; diese Verfügung erwuchs mangels Einspruch in Rechtskraft. Gleichentags vereinbarte die Ausgleichskasse mit R._ auf dessen Vorschlag hin einen Tilgungsplan, welcher auf Grund finanzieller Engpässe mehrmals angepasst wurde. Auf ein neuerliches Gesuch vom 18. Februar 2003 um Reduzierung der Teilzahlungen hin verfügte die Ausgleichskasse am 20. Februar 2003 einen Tilgungsplan, in welchem die letzte Rate am 10. Dezember 2004 zu begleichen wäre. Im Einspracheentscheid vom 24. April 2003 hielt sie daran fest. Sie begründete dies damit, der Tilgungsplan sei den finanziellen und persönlichen Verhältnissen des Pflichtigen anzupassen und die Raten seien so festzusetzen, dass die Schuld in möglichst kurzer Zeit, jedenfalls aber vor Ablauf der Vollstreckungsverwirkung am 31. Dezember 2004 beglichen sei.
B. Die hiegegen erhobene Beschwerde hiess das Versicherungsgericht des Kantons St. Gallen mit Entscheid vom 26. September 2003 teilweise gut, indem es auf eine massgebende zehnjährige Vollstreckungsverwirkung erkannte, und wies die Sache zur Festsetzung der neuen Raten an die Ausgleichskasse zurück.
C. R._ führt Verwaltungsgerichtsbeschwerde mit dem sinngemässen Begehren, es seien der vorinstanzliche Entscheid sowie die Schadenersatzverfügung vom 31. Mai 1999 aufzuheben. Die Ausgleichskasse beantragt in ihrer Stellungnahme die Aufhebung des vorinstanzlichen Entscheids unter Bestätigung ihres Einspracheentscheids vom 24. April 2003. Das Bundesamt für Sozialversicherung (BSV) verzichtet auf eine Vernehmlassung.

Das Eidg. Versicherungsgericht zieht in Erwägung:
1.1 1.1.1 Bei Erlass ihrer Verfügung vom 20. Februar 2003 ist die Ausgleichskasse von einer absoluten Frist der Vollstreckungsverwirkung von fünf Jahren ausgegangen; dementsprechend hat sie die Rückzahlung in zehn Raten zu Fr. 1700.-, elf Raten zu Fr. 2900.- sowie einer Schlussrate von Fr. 2430.50 festgelegt. Nach Ansicht der Vorinstanz verwirkt die rechtskräftig festgesetzte Schadenersatzforderung nach Ablauf von zehn Jahren; demnach könne die Ausgleichskasse tiefere Raten zugestehen. Es stellt sich somit die Frage, ob der Beschwerdeführer an der Änderung des vorinstanzlichen Entscheids überhaupt ein schutzwürdiges Interesse hat.
1.1.2 Nach Art. 103 lit. a in Verbindung mit Art. 132 OG ist zur Verwaltungsgerichtsbeschwerde an das Eidgenössische Versicherungsgericht berechtigt, wer durch die angefochtene Verfügung berührt ist und ein schutzwürdiges Interesse an deren Aufhebung oder Änderung hat. Die Rechtsprechung betrachtet als schutzwürdiges Interesse im Sinne von Art. 103 lit. a OG jedes praktische oder rechtliche Interesse, welches eine von einer Verfügung betroffene Person an deren Änderung oder Aufhebung geltend machen kann. Das schutzwürdige Interesse besteht somit im praktischen Nutzen, den die Gutheissung der Beschwerde dem Verfügungsadressaten verschaffen würde, oder - anders ausgedrückt - im Umstand, einen Nachteil wirtschaftlicher, ideeller, materieller oder anderweitiger Natur zu vermeiden, welchen die angefochtene Verfügung mit sich bringen würde. Das rechtliche oder auch bloss tatsächliche Interesse braucht somit mit dem Interesse, das durch die von der beschwerdeführenden Person als verletzt bezeichnete Norm geschützt wird, nicht übereinzustimmen. Immerhin wird verlangt, dass die Person durch die angefochtene Verfügung stärker als jedermann betroffen sei und in einer besonderen, beachtenswerten, nahen Beziehung zur Streitsache stehe (<ref-ruling> Erw. 1b, 82 Erw. 3a/aa, 125 V 342 Erw. 4a, je mit Hinweisen).
1.1.3 Durch den kantonalen Entscheid sind die einzelnen Raten nicht festgelegt worden. Da sich jedoch die Vollstreckungsverwirkung massgeblich auf die Höhe der Rückzahlungsraten auswirkt, ist davon auszugehen, dass die angeordnete Rückweisung an die Ausgleichskasse zu tieferen Einzelraten führen wird (vgl. auch die wiedererwägungsweise wieder aufgehobene Verfügung vom 14. November 2003). Insoweit ist der Beschwerdeführer nicht beschwert. Indessen verlängert sich durch die zehnjährige Dauer der Vollstreckungsverwirkung auch die Pflicht zur Rückzahlung entsprechend; dies bedeutet, dass der nach fünf Jahren noch unbezahlt gebliebene Betrag weiter eingefordert werden kann, währenddem er bei Geltung einer fünfjährigen Frist nach deren Ablauf verfällt und uneinbringlich wird. In diesem Sinne hat der Beschwerdeführer ein schutzwürdiges Interesse an der Aufhebung des vorinstanzlichen Entscheids, und es ist auf die Verwaltungsgerichtsbeschwerde einzutreten.
1.2 Weil sich die dem strittigen Tilgungsplan zugrunde liegende Schadenersatzverfügung vom 31. Mai 1999 nur auf Bundessozialversicherungsbeiträge bezieht, kann auf die Verwaltungsgerichtsbeschwerde bezüglich der Festsetzung der Raten vollumfänglich eingetreten werden (<ref-ruling> Erw. 1 mit Hinweis).
1.3 Da die Schadenersatzverfügung vom 31. Mai 1999 in Rechtskraft erwachsen ist, kann auf Rügen, welche den Bestand der Schadenersatzpflicht betreffen, nicht eingetreten werden.
1.4 Der Beschwerdeführer rügt in seiner Verwaltungsgerichtsbeschwerde, die Ausgleichskasse habe ihm erneut einen Tilgungsplan zukommen lassen (Verfügung vom 14. November 2003), obwohl der kantonale Entscheid noch gar nicht rechtskräftig sei. Nachdem die Ausgleichskasse diese Verfügung mit Wiedererwägung vom 3. Dezember 2003 aufgehoben hat, ist darauf nicht weiter einzugehen.
2. Die strittige Verfügung hat nicht die Bewilligung oder Verweigerung von Versicherungsleistungen zum Gegenstand. Das Eidgenössische Versicherungsgericht prüft daher nur, ob das vorinstanzliche Gericht Bundesrecht verletzte, einschliesslich Überschreitung oder Missbrauch des Ermessens, oder ob der rechtserhebliche Sachverhalt offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt wurde (Art. 132 in Verbindung mit Art. 104 lit. a und b sowie Art. 105 Abs. 2 OG).
3. Zu prüfen ist die Frage, ob die Vollstreckungsverwirkung für Schadenersatzforderungen nach <ref-law> fünf oder zehn Jahre beträgt.
3.1 Das AHVG regelt in Art. 16 Abs. 2 lediglich die Vollstreckungsverwirkung der rechtskräftig festgesetzten Beitragsforderungen. Für die Vollstreckungsverwirkung einer rechtskräftigen Schadenersatzforderung nach <ref-law> ist nach der Rechtsprechung <ref-law> sinngemäss anwendbar (ZAK 1991 S. 129 Erw. 2c, gestützt auf Urteil R. vom 14. April 1986, H 74/85; vgl. auch Urteil K. vom 5. Februar 2003, H 183/01, sowie Urteil G. vom 27. Mai 2002, H 281/01). Diese Rechtsprechung wurde in der Lehre kritisiert: Knus geht bei der Frage der Vollstreckungsverwirkung der Schadenersatzverfügung von einer echten Lücke aus und postuliert die analoge Anwendung von <ref-law>. Einerseits entspreche die zehnjährige Frist am ehesten Sinn und Zweck von <ref-law>; andererseits werde damit eine Vereinheitlichung des Schadenersatzes in Privat- und AHV-Recht erreicht, nachdem auch das mit <ref-law> verwandte Verantwortlichkeitsgesetz häufig auf das Privatrecht Bezug nehme. Zudem setze die Schadenersatzpflicht im Gegensatz zu den Beitrags- und Rückerstattungsforderungen ein Verschulden voraus. Weiters sei der Schadenersatz im Rahmen des AHV-Rechts fremd und einzigartig, weshalb es sich rechtfertige, wie bei einem anderen Ausnahmefall (Rückforderungsanspruch des Nichtversicherten auf bezahlte Beiträge) die zehnjährige Frist anzuwenden (Knus, Die Schadenersatzpflicht des Arbeitgebers in der AHV, Diss. Zürich, Winterthur 1989, S. 71 ff.). Nussbaumer kritisiert mit Knus die Rechtsprechung zur analogen Anwendung von <ref-law> (Die Ausgleichskasse als Partei im Schadenersatzprozess nach <ref-law>, ZAK 1991 S. 440). Die Vorinstanz hat unter Einbezug dieser Kritik sowie unter Berücksichtigung der Umstände, dass das Verfahren nach <ref-law> sich von jenem der Beitragsfestsetzung und des Beitragsbezugs unterscheidet und auch keine Abgabestreitigkeit im Sinne von Art. 114 OG darstellt, auf eine zehnjährige Vollstreckungsverwirkungsfrist erkannt.
Nach dem Gesagten ist die Beibehaltung der Rechtsprechung zur analogen Anwendung von <ref-law> zu überprüfen.
3.2 Im nicht publizierten Urteil R. vom 14. April 1986, mit welchem die analoge Anwendung von <ref-law> auch für die Vollstreckungsverwirkung bei Schadenersatzforderungen für anwendbar erklärt wurde (bestätigt in ZAK 1991 S. 129 Erw. 2c), stützte sich das Gericht auf die ebenfalls analoge Anwendung von <ref-law> bei Rückerstattungsforderungen (<ref-ruling> Erw. 2c) und führte aus, die Herbeiziehung von <ref-law> bei Schadenersatzforderungen sei umso gerechtfertigter, als es sich beim Schadenersatz um entgangene Beiträge handle; den Einwand des BSV, beim Schadenersatz gehe es oft um hohe Summen, weshalb den Verantwortlichen längere Fristen zuzugestehen seien, wies das Gericht ab, weil auch Rückerstattungsforderungen hohe Beträge zum Gegenstand haben könnten. Nachdem in erster Linie der Umstand, dass der Schadenersatzforderung Beitragsverluste zugrunde liegen, für die analoge Anwendung von <ref-law> spricht (vgl. Nussbaumer, a.a.O., S. 440) und das Eidgenössische Versicherungsgericht in konstanter Praxis den Unterschied von Schadenersatz- und Beitragsforderung betont hat (<ref-ruling> Erw. 4c mit Hinweisen), erscheint die Rechtsprechung von ZAK 1991 S. 129 Erw. 2c nicht folgerichtig und es kann an ihr nicht weiter festgehalten werden. Daran ändert auch <ref-ruling> nichts: In jenem Fall waren Verzugszinsen streitig; diese sind akzessorisch zu den Beiträgen und damit untrennbar mit diesen verbunden, was auf eine Schadenersatzforderung gerade nicht zutrifft. Mit der Vorinstanz ist zudem darauf hinzuweisen, dass das Verfahren zur Geltendmachung des Schadenersatzes sich wesentlich vom Beitragsverfahren unterscheidet (AHI 1996 S. 131 Erw. 2c mit Hinweisen); es stellt auch keine Abgabestreitigkeit im Sinne von Art. 114 OG dar (<ref-ruling> Erw. 2b mit Hinweisen).
3.3 Das seit 1. Januar 2003 in Kraft stehende Bundesgesetz über den Allgemeinen Teil des Sozialversicherungsrechts vom 6. Oktober 2000 (ATSG) sieht für die vorliegende Fragestellung keine Lösung vor. <ref-law> (Erlöschen des Anspruchs) erfasst nur ausstehende, nicht jedoch bereits rechtskräftig festgesetzte Leistungen und Beiträge (Kieser, ATSG-Kommentar, Zürich 2003, N 3 f. zu Art. 24). <ref-law> handelt hingegen von der Rückerstattung von Leistungen und Beiträgen und bezieht sich somit auch nicht explizit auf Schadenersatzforderungen. Bei <ref-law> (Verantwortlichkeit) hat der Gesetzgeber dessen Anwendung im Verfahren nach <ref-law> ausgeschlossen (vgl. <ref-law> in der seit 1. Januar 2003 geltenden Fassung sowie Kieser, a.a.O., N 16 zu Art. 78). <ref-law> in der seit 1. Januar 2003 geltenden Fassung behandelt lediglich die Festsetzungs-, nicht jedoch die Vollstreckungsfrist, wobei der Gesetzgeber diese Fristen neu als Verjährungs- und nicht mehr als Verwirkungsfristen behandelt wissen will (vgl. BBl 1994 V 983 f.).
Auch aus der gescheiterten 11. AHV-Revision ergeben sich keine neuen Anhaltspunkte: <ref-law> sollte dahin gehend ergänzt werden, als dass <ref-law> (Verjährung des Verlustscheins) nicht anwendbar sei, und die vorgesehene Fassung von <ref-law> äusserte sich ebenfalls nur zur Festsetzungs- nicht jedoch zur Vollstreckungsfrist.
Somit lässt sich weder aus der Einführung des vorliegend nicht direkt anwendbaren Bundesgesetzes über den Allgemeinen Teil des Sozialversicherungsrechts (<ref-ruling> Erw. 1.2 mit Hinweisen) noch aus der Neuformulierung des <ref-law> etwas zur Beantwortung der Frage gewinnen.
3.4 Nebst der analogen Anwendung von <ref-law> bietet sich einzig diejenige der allgemeinen Verjährungsfrist von <ref-law> an, welche bei Anerkennung der Forderung durch Ausstellung einer Urkunde oder Feststellung der Schuld durch ein richterliches Urteil eine zehnjährige Frist vorsieht. Die Anwendung dieser längeren Frist entspricht denn auch Sinn und Zweck von <ref-law>, da Schadenersatzforderungen oft fünf- oder sechsstellige Summen ausmachen und deshalb häufig nicht innert einer fünfjährigen Frist abbezahlt werden können, sodass die Ausgleichskassen wiederum eines Teils ihrer Ansprüche verlustig gehen und der Zweck der Schadloshaltung demnach nur teilweise erreicht wird (vgl. hiezu bereits die Bedenken des BSV im Urteil R. vom 14. April 1986, H 74/85, sowie Knus, a.a.O., S. 72). Andererseits besteht aus Sicht der Rechtssicherheit kein Bedürfnis an einer kurzen Frist, weil die Verhältnisse nach der rechtskräftigen Festsetzung des Schadenersatzes (Verwaltungsverfügung oder richterliches Urteil) klar sind, der geschuldete Betrag feststeht und es keine Beweisschwierigkeiten wegen Zeitablaufs mehr zu gewärtigen gibt. In diesem Zusammenhang ist auch auf die neuere Rechtsprechung des Eidgenössischen Versicherungsgerichts hinzuweisen, wonach die Vollstreckung einer rechtskräftig festgesetzten Witwenabfindung (<ref-ruling>) respektive rechtskräftig zugesprochener Leistungen der Invalidenversicherung (SVR 2002 IV Nr. 15 S. 47) einer zehnjährigen Frist unterliegt. Im Übrigen stellt jede kürzere als die zehn Jahre dauernde Frist eine Privilegierung des Schadenersatzschuldners dar; denn es ist nicht nachvollziehbar, weshalb dieser aus Verschulden Haftende für den von ihm verursachten Schaden nicht ebenso lange soll belangt werden können wie für jede andere Forderung (vgl. <ref-law>).
4. Für den hier zu beurteilenden Fall bedeutet dies, dass die Vorinstanz zu Recht von einer zehnjährigen Verwirkungsfrist ausgegangen und die Sache zur Neuberechnung der Raten an die Ausgleichskasse zurückgewiesen hat.
5. Da es nicht um die Bewilligung oder Verweigerung von Versicherungsleistungen geht, ist das Verfahren kostenpflichtig (Art. 134 OG e contrario). Der unterliegende Beschwerdeführer hat demnach die Gerichtskosten zu tragen (Art. 156 Abs. 1 in Verbindung mit Art. 135 OG).

Demnach erkennt das Eidg. Versicherungsgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt und mit dem geleisteten Kostenvorschuss verrechnet.
3. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Bundesamt für Sozialversicherung zugestellt.
Luzern, 22. Oktober 2004
Im Namen des Eidgenössischen Versicherungsgerichts
Der Präsident der I. Kammer: Die Gerichtsschreiberin: