<p>I'm considering Altova MapForce (or something similar) to produce either XSLT and/or a Java or C# class to do the translation. Today, we pull data right out of the database and manually build an XML string that we post to a webservice. </p>

<p>Should it be db -> (internal)XML -> XSLT -> (External)XML? What do you folks do out there in the wide world?</p>

I would use one of the out-of-the-box XML serialization classes to do your internal XML generation, and then use XSLT to transform to the external XML.  You might generate a schema as well to enforce that the translation code (whatever will drive your XSLT translation) continues to get the XML it is expecting for translation in case of changes to the object breaks things.
There are a number of XSLT editors on the market that will help you do the mappings, but I prefer to just use a regular XML editor.