You could say "prospective clients"

I'm having trouble coming up with a one-word answer. The essence of cold calling is that you are calling, specifically, strangers whom you have never talked to before. "Strangers" is the best can think of at the moment: Cold calling means calling strangers who have never been clients before.

I think the word could be "relations" - you have no relations with this company. Although it's a bit confusing because you say you have no relations with that "partner" - partner implies that you do have relations, since you're partners in business? Did you mean to say "with that part"? That phrase is not so commonly used, it would be better to state clearly who you don't have relations with. I'm not sure at all about the second sentence, is cold-calling a thing? ;D Someone else will have to explain that.

Cold calling means calling prospective clients.