The following are less commonly used, but improve on my prior answer
Client certificates
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
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
VPN
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.
Warning for Javascript users
Don't attempt to use SOAP with message security with Javascript. There is no way to securely create and manage the key pair that is needed for SOAP messages. In addition there are several other concerns such as cross-domain usage, XML parsing, etc.