A Salesforce Sandbox doesn't currently provide the same level of Callout SOAP tracing that a development environment does. I've found that by using SOAP UI I can easily create a Mock Service from the WSDL and redirect the Salesforce Endpoint there to see the outbound SOAP messages.
Before you read any further. Go to Salesforce Ideas: View Callout Request and Response XML in Sandbox and promote it so that Salesforce can extend the Sandbox to include the callout xml.
Steps to trace Salesforce Callout SOAP with SOAP UI
- Save the WSDL and import it into Salesforce
- Add the mock service as a remote site in Salesforce
- Change the endpoint_x in Apex to the mock service URL