Yes, as you suggested, you could send them a string of bytes ( in this context we might call it a challenge text) and have them encrypt it with their server's SSL/TLS private key and send back the ciphertext, then you can verify it by decrypting it with the public key from their SSL/TLS server cert.
Or you could generate a string of bytes, encrypt it with the public key from their server cert, send it to them, have them decrypt it with their server's private key, and have them send you back the original cleartext.
Note, though, that relatively few people know how to do things like this with their SSL private key, so don't be surprised if you have to provide them with step-by-step instructions for finding their private key and encrypting or decrypting your challenge.