With a bit of web searching we found that dwmapi.dll is only present on Vista and later machines. Since we weren't using that dll directly it shouldn't be the cause of our issue on Windows XP.
At this point it would appear we have all necessary dlls and that our problem must be elsewhere. The documentation on Dependency Walker, however, provides some useful information:
When a module is first opened by Dependency Walker, it is immediately scanned for all implicit, delay-load, and forwarded dependencies. Once all the modules have been scanned, the results are displayed. In addition to these known dependencies, modules are free to load other modules at run-time without any prior warning to the operating system. These types of dependencies are known as dynamic or explicit dependencies. There is really no way to detect dynamic dependencies without actually running the application and watching it to see what modules it loads at run-time.
Version 2.0 and later of Dependency Walker provides a Profile option from the menu. If you have a dll loaded, however, the item is disabled - you have to load an executable first.
For this to work, you need to load regsvr32.exe, which will enable the menu items. Once done, select Profile > Start Profiling to bring up the Profile Module dialog. The only necessary change is to add the dll being registered to the "Program arguments" setting.
Press OK and wait for the application to run. Eventually you will see the usual registration error message box, which you can simply click to continue. Once finished, scrolling through the results shows a couple errors for mssoapr3.dll.
The first error states that the file path specified can't be found. Double-clicking the error shows that it is looking for the dll under "c:\temp\1033". The second states that it cannot find the file - this time in the same folder as the dll we tried to register. So it seems either location is valid for this particular dependency.
Once we add mssoapr3.dll to the same folder, mssoap30.dll registers without issue.