Ssl – Add SSL certificate after curl error: “unable to get local issuer certificate”

I'm trying to access a partners SOAP API, for that goal I made a CSR and received a CRT. I've made a PEM file with my key and the CRT:

cat mycert.crt mykey.key > mycertandkey.pem

When I try to hit the service with curl:

curl --verbose --cert mycertandkey.pem https://partner/service?wsdl
* Hostname was NOT found in DNS cache
*   Trying IP.IP.IP.IP...
* Connected to PARTNER (IP.IP.IP.IP) port 443 (#0)
* successfully set certificate verify locations:
*   CAfile: none
  CApath: /etc/ssl/certs
* SSLv3, TLS handshake, Client hello (1):
* SSLv3, TLS handshake, Server hello (2):
* SSLv3, TLS handshake, CERT (11):
* SSLv3, TLS alert, Server hello (2):
* SSL certificate problem: unable to get local issuer certificate
* Closing connection 0
curl: (60) SSL certificate problem: unable to get local issuer certificate
More details here: http://curl.haxx.se/docs/sslcerts.html

curl performs SSL certificate verification by default, using a "bundle"
 of Certificate Authority (CA) public keys (CA certs). If the default
 bundle file isn't adequate, you can specify an alternate file
 using the --cacert option.
If this HTTPS server uses a certificate signed by a CA represented in
 the bundle, the certificate verification probably failed due to a
 problem with the certificate (it might be expired, or the name might
 not match the domain name in the URL).
If you'd like to turn off curl's verification of the certificate, use
 the -k (or --insecure) option.

Now when I try with the -k option everything works fine, but I'd rather add their current SSL certificate so I can connect without the -k option.

I'd like to try the second option in the following answer but haven't managed so far: https://stackoverflow.com/a/24618403/2730032

I retrieved different certificates from my partners service with openssl like in: https://stackoverflow.com/a/7886248/2730032

Afterwards I tried adding these certificates to my server with https://superuser.com/a/437377

But so far I still cannot get curl to work without the -k flag. Am I wrong in how I retrieve the needed certificate or in how I add it to my system? Or am I mistaken in my general approach?

EDIT 1: This is what happens when I try to get the certificates via SSL

openssl s_client -showcerts -connect PARTNER:443 </dev/null
CONNECTED(00000003)
depth=0 O = PARTNER_INFO, OU = PARTNER_INFO, CN = PARTNER_INFO
verify error:num=20:unable to get local issuer certificate
verify return:1
depth=0 O = PARTNER_INFO, OU = PARTNER_INFO, CN = PARTNER_INFO
verify error:num=27:certificate not trusted
verify return:1
depth=0 O = PARTNER_INFO, OU = PARTNER_INFO, CN = PARTNER_INFO
verify error:num=21:unable to verify the first certificate
verify return:1
---
Certificate chain
 0 s:/O=PARTNER_INFO/OU=PARTNER_INFO/CN=PARTNER_INFO
   i:/C=PARTNER_INFO/ST=PARTNER_INFO/L=PARTNER_INFO/O=PARTNER_INFO/OU=PARTNER_INFO/CN=PARTNER_INFO CA/emailAddress=PARTNER_INFO
-----BEGIN CERTIFICATE-----
CERTIFICATE1
-----END CERTIFICATE-----
 1 s:/C=US/O=VeriSign, Inc./OU=VeriSign Trust Network/OU=Terms of use at https://www.verisign.com/rpa (c)10/CN=VeriSign Class 3 Secure Server CA - G3
   i:/C=US/O=VeriSign, Inc./OU=VeriSign Trust Network/OU=(c) 2006 VeriSign, Inc. - For authorized use only/CN=VeriSign Class 3 Public Primary Certification Authority - G5
-----BEGIN CERTIFICATE-----
CERTIFICATE2
-----END CERTIFICATE-----
 2 s:/C=US/O=VeriSign, Inc./OU=VeriSign Trust Network/OU=(c) 2006 VeriSign, Inc. - For authorized use only/CN=VeriSign Class 3 Public Primary Certification Authority - G5
   i:/C=US/O=VeriSign, Inc./OU=Class 3 Public Primary Certification Authority
-----BEGIN CERTIFICATE-----
CERTIFICATE3
-----END CERTIFICATE-----
---
Server certificate
subject=/O=PARTNER_INFO/OU=PARTNER_INFO/CN=PARTNER_INFO
issuer=/C=PARTNER_INFO/ST=PARTNER_INFO/L=PARTNER_INFO/O=PARTNER_INFO/OU=PARTNER_INFO/CN=PARTNER_INFO CA/emailAddress=PARTNER_INFO
---
No client certificate CA names sent
---
SSL handshake has read 3872 bytes and written 503 bytes
---
MORE INFO...

I've also tried openssl s_client -showcerts -key mycertandkey.pem -connect PARTNER:443 </dev/null but it gives me the same results (and certificates).

EDIT 2: As I've commented in the only answer so far: the partner in question added a Gandi CA to their server (at least that's what they tell me) and it now works. So it seems since their certificate is now signed by a CA that is in my default CA bundle I can now get curl to work without the -k flag. However it would be nice to know how I could've corrected the problem on my end.