Having spent lots of time googling and going down various blind alleys, trying to fix an error on our live site servers where trying to run a DTS, looking at user properties and various other things all threw up a pretty uninformative error related to being unable to find xpstar.dll. Having sorted it I thought I'd post what worked for me in case it saves anyone else from too much time-wasting.
The root of the problem was the virus and trojan s***storm that hit us a few weeks back, but once that was remedied the SQL Server 2000 issues remained.
For a while I was looking on the wrong server, coz I assumed that the server running the DTS would be requiring its own copy, but turns out that the server it was targetting was the one lacking xpstar. Don't forget to check the other server!
Plopping a new copy of it into the relevant place didn't help. Perhaps it needed re-registering in some way. A couple of threads in Googledom talked about MDAC, and reinstalling it seemed like a good idea, but fooling round looking for Windows Components to reinstall led nowhere.
One of those threads mentioned reinstalling SP4. Fortunately we had copies of the installation media for both SP4 and SQL Server 2000 on the server, but first time we ran the SP4 install it transpired that the virus had actually messed with about with these too, deleting a crucial directory (Binn), not within the SP4 media but the SQL installation media. Once this was sorted out, an SP4 reinstallation was all that was required. It fixed the xpstar error without a restart.
Don't know if there is a lesson four, but if it turns out that we didn't get the virus off properly, or I should have done a restart after all, I'll let you know.
January 2010: we had more problems which in part were related to, you guessed it, xpstar.dll "disappearing". All the SQL Server jobs disappeared, for one. Reapplying SP4 once more did the trick: turned out the jobs were just hiding when the server "lost" xpstar. I need to get to the bottom of why it happened a second time, but there you go: SP4 fix definitely works for us.