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. 