the run command doesn't necessarily use cmd.exe
It would only do that if you were to type cmd.exe /k dosomecommand
so that really depends on what you're trying to run from the start --> run prompt
It maybe possible that something like rundll32 is corrupt *shrug* (again maybe helped by reinstalling sp4, or just installing it if you haven't yet)
To get rid of the cmd32.exe prompt at startup, you can run an app like
Startupcpl for windows 2000
Just like msconfig for win9x/XP