Just to finish the thread and let everyone know what happened: We ended up having to call MS Tech Support. No new hardware was installed, no new software either (except MS's SP4). The tech spent about 9 hours on the phone with the other tech guy here and didn't get it resolved. The MS Tech said they are having problems with SP4 on server machines running MS Server 2000 and he will try to get some kind of a fix as soon as they can find the problem in their labs.
Thanks for everyones help!