This is sort of a Java problem, rather than an entirely Salesforce-specific problem, so depending on how you search for the answer, it could take you a while to get to why it failed, and what the actual solution is.
Basically: The Java used by Salesforce/Apex for SSL handshaking requires that the server certificate has a SAN (Subject Alternative Name) that matches the CN (Common Name) when the CN is an IP Address. This isn't an issue when the CN is a Hostname.
As such, as you can't use any of the (not particularly nice anyway) java workarounds for this issue; the solution to this involves generating a new server certificate with extra info on it. If you control the web service you're calling out to, that should be reasonably easy - otherwise you will need to get in touch with whoever administers the server and its certs and ask them to do this, as this is a definite blocker with no known workarounds in Salesforce (unless anyone else wants to chime in with one!).
Either way, someone will need to pay for a new Public CA signed server certificate to replace the old one. Depending on your Public CA, you will need to make sure you are buying a cert type that allows SANs, and be aware there may be extra charges per SAN added, depending on your provider.
To include the required SAN using Java 7's keytool, use the flag -ext san=ip:0.0.0.0 - filling in the appropriate IP address here, that matches the CN IP address, instead of 0.0.0.0.
To include the required SAN using openssl, include the following in your openssl.conf file used for generation
[req]
req_extensions = v3_req
[v3_req]
subjectAltName = @alt_names
[alt_names]
IP.1 = 0.0.0.0
Again, filling in the appropriate IP address that matches your CN, instead of 0.0.0.0
The Java flavoured Q&A can be found at https://stackoverflow.com/questions/8443081/
Best Answer
Per the documentation you linked:
Self-signed certificates will not work, because there must be a trusted root CA at the end of the certificate chain. However, it doesn't have to be a cert signed directly from a CA. Assuming you already have a CA-issued certificate, you can create a new certificate and sign it with your certificate that you received from the CA (thus creating a chain of trust), and then you can validate against this other certificate. You'll need to include all certificates in the chain, except for the root, as outlined in that documentation. You may create a certificate solely for this mutual authentication method, but it must be signed by a higher authority.