...
<element name="updatePLZInformationen">
<complexType>
 <sequence>
  <element name="clientid" nillable="true"
   type="xsd:string" />
  <element name="securitytoken" nillable="true"
   type="xsd:string" />
  <element maxOccurs="unbounded" minOccurs="0"
   name="plzinfos" type="tns2:PLZInfo" />
 </sequence>
</complexType>
</element>
...
<complexType name="PLZInfo">
 <sequence>
  <element name="kurzname" nillable="true"
   type="xsd:string" />
  <element name="plz" nillable="true"
   type="xsd:string" />
  <element name="stadt" nillable="true"
   type="xsd:string" />
  <element name="status" nillable="true"
   type="xsd:string" />
  <element name="typ" nillable="true"
   type="xsd:string" />
  <element name="zusatz" nillable="true"
   type="xsd:string" />
 </sequence>
</complexType>

##</code><code>##

#!/usr/bin/perl -w
use SOAP::Lite +trace => 'debug';
my $plz = SOAP::Lite
    -> service('file:/home/orca/oracle/DataSyncTool/config/SKADataService.wsdl');
 
$plz->updatePLZInformationen(SOAP::Data->type("xsd:string")->name("clientid" => "test")->value,
        SOAP::Data->type("xsd:string")->name("securitytoken" => "test")->value,
        SOAP::Data->type("tns2:PLZInfo")->name("plzinfos")->value(
              SOAP::Data->name("kurzname")->type("xsd:string")->value("gargel"),
              SOAP::Data->name("plz")->type("xsd:string")->value("12345"),
              SOAP::Data->name("stadt")->type("xsd:string")->value("Musterstadt"),
              SOAP::Data->name("status")->type("xsd:string")->value("0815"),
              SOAP::Data->name("typ")->type("xsd:string")->value("2"),
              SOAP::Data->name("zusatz")->type("xsd:string")->value("hinten rechts"))->value);

##</code><code>##

<?xml version="1.0" encoding="UTF-8"?>
<soap:Envelope 
xmlns:wsdlsoap="..." 
xmlns:tns2="...e" 
soap:encodingStyle="http://schemas.xmlsoap.org/soap/encoding/" 
xmlns:soap="..." 
xmlns:wsdl="..." 
xmlns:impl="..." 
xmlns:xsi="..." 
xmlns:soapenc="..." 
xmlns:xsd="http://www.w3.org/2001/XMLSchema">
<soap:Body><impl:updatePLZInformationen>
<clientid xsi:type="xsd:string">test</clientid>
<securitytoken xsi:type="xsd:string">test</securitytoken>
<plzinfos xsi:nil="true" xsi:type="tns2:PLZInfo" /> <-- here's the problem!!!
<plz xsi:type="xsd:string">12345</plz>
<stadt xsi:type="xsd:string">Musterstadt</stadt>
<status xsi:type="xsd:string">0815</status>
<typ xsi:type="xsd:string">2</typ>
<zusatz xsi:type="xsd:string">hinten rechts</zusatz>
</impl:updatePLZInformationen>
</soap:Body>
</soap:Envelope>