Creating sessionId is working fine:

https://developer.salesforce.com/docs/atlas.en-us.live_agent_rest.meta/live_agent_rest/live_agent_rest_SessionId.htm

I am trying to create a chat visitor session but I am getting the error: "Session required but was invalid or not found". 
https://developer.salesforce.com/docs/atlas.en-us.live_agent_rest.meta/live_agent_rest/live_agent_rest_ChasitorInit.htm

 

Headers:
  Authorization: 'Bearer xxxx',
    'X-LIVEAGENT-API-VERSION': '48',
    'X-LIVEAGENT-SESSION_KEY': 'xxxxxxxx', // key from sessionId request
    'X-LIVEAGENT-AFFINITY': 'xxxxxxxx', // affinityToken from sessionId 
    'X-LIVEAGENT-SEQUENCE': '1'

Request Body:
    sessionId: 'xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx',
    organizationId: '00Dxxxxxxxxxxxxx',
    deploymentId: '572xxxxxxxxxxxx',
    buttonId: '573xxxxxxxxxxxx',
    userAgent: '',
    language: 'en-US',
    screenResolution: '2560x1440',
    visitorName: 'Test',
    prechatDetails: [],
    prechatEntities: [],
    receiveQueueUpdates: true,
    isPost: true

When the outbound message from salesforce is initiated the following error is thrown from Salesforce end.

Delivery Failure Reason: (404)Not Found

In addition in our server log the following error is thrown.
  [nio-8080-exec-9] o.s.ws.server.EndpointNotFound           : No endpoint mapping found for [SaajSoapMessage {http://soap.sforce.com/2005/09/outbound}notifications]

For some background:
We have three endpoints defined in our application, namely for Account, Contact, and Opportunity entities of Salesforce. All three of our servers are having the same namespace and the same notification data type. In order to differentiate the messages we have different tags for <soap:operation soapAction=""/> for each web service in the wsdl.

Our services works fine when tested with a SOAP testing tool, eg: SOAP UI. We have tested for all three entities successfully. The error is only when it is initiated from Salesforce via outbound messages which are fired from a workflow rule.

Why does this error occur when fired directly from Salesforce but not from SOAP UI? And what is causing this error?