The following are less commonly used, but improve on my prior answer
A client certificate will encrypt the entire TLS session with "mutual authentication" and will protect the session from MITM attacks and can be used over untrusted networks.
Use DNSSec for all DNS domains used in the application, namely the location of the service, and all CRLs, AIAs, and OCSP paths in the chain
API calls over a VPN may improve security, and if the VPN requires locally deployed certificates the security benefit may be the same as client certificates.
A variation of this answer is to use ToR with the target server having a .onion address, but isn't recommended for the general public.
If the web service is using SOAP, or WS-Security consider using message security. Message security has been described as the WS-* interpretation of TLS but within an XML payload. That means that these SOAP calls can be used over plain HTTP and relayed over several untrusted intermediaries.