After some Help, we found the issue to be in a misconfiguration of the webapplication, which somehow broke the policy validation

Hello and thank you for your help, 

sadly this still does not work. I checked my policy which I sadly didnt include in my first post and it is identical to the one you provided. 

After doing the steps you asked in soap ui the result in the ^iscsoap log looks kind of the same: 

05/18/2020 10:26:51 *********************
Input to Web service with SOAP action = "Test"
<soapenv:Envelope xmlns:out="http://soap.sforce.com/2005/09/outbound" xmlns:soapenv="http://schemas.xmlsoap.org/soap/envelope/" xmlns:urn="urn:sobject.enterprise.soap.sforce.com">
   <soapenv:Header xmlns:wsa="http://www.w3.org/2005/08/addressing">
      <wsse:Security soapenv:mustUnderstand="1" xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd" xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
         <wsu:Timestamp wsu:Id="TS-2667979931FBF3824915897900793112">
            <wsu:Created>2020-05-18T08:21:19.311Z</wsu:Created>
            <wsu:Expires>2020-05-19T12:07:59.311Z</wsu:Expires>
         </wsu:Timestamp>
         <wsse:UsernameToken wsu:Id="UsernameToken-2667979931FBF3824915897900699691">
            <wsse:Username>someuser</wsse:Username>
            <wsse:Password Type="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-username-token-profile-1.0#PasswordText">somepassword</wsse:Password>
            <wsse:Nonce EncodingType="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-soap-message-security-1.0#Base64Binary">BvWIisN0trJYs54oV8TRpQ==</wsse:Nonce>
            <wsu:Created>2020-05-18T08:21:09.967Z</wsu:Created>
         </wsse:UsernameToken>
      </wsse:Security>
      
   <wsa:Action>Test</wsa:Action></soapenv:Header>
   <soapenv:Body>
      <out:notifications>
         <out:OrganizationId>1234567890ABCDEFGH</out:OrganizationId>
         <out:ActionId>1234567890ABCDEFGH</out:ActionId>
         <out:SessionId>123</out:SessionId>
         <out:EnterpriseUrl>www.test.de</out:EnterpriseUrl>
         <out:PartnerUrl>www.partnertest.de</out:PartnerUrl>
         <out:Notification>
            <out:Id>1234567890ABCDEFGH</out:Id>
            <out:sObject>
               <urn:Id>1234567890ABCDEFGH</urn:Id>
               <urn:Name__c>Testington</urn:Name__c>
            </out:sObject>
         </out:Notification>
      </out:notifications>
   </soapenv:Body>
</soapenv:Envelope>
---------------
Validate Security header: action="Test"
Validating security element 1: %SOAP.Security.Timestamp
Security TimeStamp validated
Validating security element 2: %SOAP.Security.UsernameToken
Security UsernameToken validated
Security SSL message 05/18/2020 10:26:52 *********************
Validation Policy 2 in OBG.EnsWSP.EnsBS.SFSoapServiceConfig:service for OBG.EnsWSP.EnsBS.SFSoapService
Headers:
  Header Namespace=http://www.w3.org/2005/08/addressing, Name=Action, Id= Tokens: Signatures: SignatureConfirmations: EncryptedData: Timestamp Id=, pos= *********************
Alternatives Alternative 1
    sp:TransportBinding
        sp:IncludeTimestamp
        sp:AlgorithmSuite=Basic128
    Supporting Tokens
        UsernameToken
            :type=sp:SignedSupportingTokens
            Include=AlwaysToRecipient
            wss=1.1
    wsap:UsingAddressing Supporting Token 1, type=sp:SignedSupportingTokens, tokenType=UsernameToken
     Token not found
    Validate of TransportBinding failed.
    No Alternative matches
05/18/2020 10:26:52 *********************
Output from Web service with SOAP action = "Test"
<?xml version='1.0' encoding='UTF-8' standalone='no' ?>
<SOAP-ENV:Envelope xmlns:SOAP-ENV='http://schemas.xmlsoap.org/soap/envelope/' xmlns:xsi='http://www.w3.org/2001/XMLSchema-instance' xmlns:s='http://www.w3.org/2001/XMLSchema' >
  <SOAP-ENV:Body>
    <SOAP-ENV:Fault>
      <faultcode>SOAP-ENV:Server</faultcode>
      <faultstring>Serverapplikationsfehler</faultstring>
      <detail>
    <error xmlns='http://soap.sforce.com/2005/09/outbound'>
     <text>FEHLER #6454: Keine unterstützte Richtlinienalternative in Konfiguration OBG.EnsWSP.EnsBS.SFSoapServiceConfig:service.</text>
    </error>
</detail>
    </SOAP-ENV:Fault>
  </SOAP-ENV:Body>
</SOAP-ENV:Envelope>