I've done most of the work based on other people's code on stack overflow. See below.
My current issue is that I'm still getting authorization failure and I can clearly see why. v2 API requires X-IBM-Client-Id and X-IBM-Client-Secret to be passed as well as SOAP security header. However, I don't know how to inject it while using service created from Wsdl file.
Solved problems:
Overcame namespaces problem (using message formatter Consume WCF Royal Mail API in c# Console Application).
Solved binding configuration problem which results in two security headers. Also, you must set maxReceivedMessageSize if you want to get no exception while retrieving label.Final binding:
<system.serviceModel>
<bindings>
<basicHttpBinding>
<binding name="basicBindingTransport" maxReceivedMessageSize="2147483647">
<security mode="Transport">
</security>
</binding>
</basicHttpBinding>
</bindings>
<client>
<endpoint address="https://api.royalmail.net/shipping/v2" binding="basicHttpBinding"
bindingConfiguration="basicBindingTransport" contract="RoyalMailApiWsdl.shippingAPIPortType" name="shippingAPIPort" />
</client>
</system.serviceModel>
Solved E0007 Authorization Failure.
Solved The HTTP request is unauthorized with client authentication scheme 'Anonymous' (you must use the binding as above with security "Transport" and inject credentials directly into http post header itself (See my answer below).
And many other issues, which I cannot remember now. I hope this post will help others.