When we shipped SQL Server 2000 SP3/SP3a (32-bit) and MSDE SP3/SP3a, due to a misunderstanding, we removed the necessary MSXML 2.6 component needed by OpenXML. The effect is that if you install MSDE SP3/SP3a directly, you will not have the MSXML 2.6 component needed. And if you upgrade to SP3/SP3a directly from the RTM version, you will get an old version of MSXML 2.6 that contains some bugs that were fixed with SP2.
So you have two options:
1. When upgrading SQL Server 2000, upgrade from SP2.
2. If you already upgraded (not via SP2) or install MSDE directly, get the correct MSXML 2.6 component from the following URL:
http://support.microsoft.com/default.aspx?scid=kb;en-us;823490
Note that this needs to be installed on the server (not with MDAC).
I hope this helps someone. I at least can now point to this blog entry when answering related comments in newsgroups :-).