Ultimate Recipient is required but not present error when using WSA:Addressing

Issue

We are trying to create a Web Service call to a third party WS which requires Addressing feature to be present in the request message. However, at the moment the call is failing with the following error message. What does it mean because the Action element is present in the SOAP request.

Header http://schemas.xmlsoap.org/ws/2004/08/addressing:Action for ultimate recipient is required but not present in the message