Es kann wirklich an den Netzwerkeinstellungen liegen.
Wenn der Shutdownpatch nicht hilft, kann man mal probieren, die Netzwerktreiber komplett zu deinstallieren und dann wieder zu installieren.
Der Grund liegt daran, dass Win98 beim Beenden auch die Netzwerkverbindungen kappt. Sind diese durch die Treiber zu langsam, oder hängen durch irgendeinen Fehler, hängt auch Windows beim Runterfahren.
Ausserdem kann man noch in msconfig das schnelle Herunterfahren von Windows deaktivieren. Das kann aus Treibergründen auch zu Problemen führen (entweder ständiger Scandisk beim Hochfahren, oder beim Runterfahren wird gestreikt).
Das ganze Prozedere nehme ich mindestens einmal in der Woche bei einem Rechner auf der Arbeit auf mich, damit der User wieder glücklich und zufrieden in den Feierabend gehen kann.
(Neuinstallation ist eigentlich nie nötigt)