We encountered the same issue today after installing a new version of TSM client software which required a reboot. We have been running SQL 2000 - 8.00.2039 for over a year without this issue so it may not be related to the SP itself.

We do NOT have automatic Win2k3 updates enabled but have applied updates within the past 4 weeks and have rebooted the machine more than twice since the updates were applied.

Post SP4 hotfixes (http://support.microsoft.com/?kbid=894905) does not mention the issue.

Sorry not much help.