Hi John
In this particular instance, the Web service methods is named "RetrieveMultiple" and according to Microsoft documentation (http://msdn.microsoft.com/en-us/library/bb928434.aspx) refers to an API that uses strongly typed object so XML construct for the parameter will not work.
SI Web Parts were tested with "FetchXml" method exposed by Microsoft Dynmaic CRM 3.0. I believe CRM 4.0 continue to support this API, which allows you to construct XML parameter. It executes slower than "RetrieveMultiple" due to extra parsing but will definitely work for you. The "FetchXML" parameter is typically used in "Fetch" method which appears to be not available in that WSDL service. Any idea why it is not there?
Other than that, your constructed fetchXML string seems to be valid according to their documentation and should bring data back.