As @Holger_von_Thomsen notes, how are you creating the SOAP request? Depending upon that, an item to check:if creating the XML with pub.xml:documentToXMLString is to always set encode to true. The default is false. This can lead to XML markup characters appearing in the data that can cause parsing to fail. Markup characters that appear in the element data, typically & and <, must be escaped. (You don’t need to do this yourself – the services within IS will do so, assuming you use the right inputs.)
This is just a guess at what might be wrong. But given the statement that is sometimes works and sometimes fails seems to indicate a data-driven issue.