Do I just need to start cold calling companies that based on their name “might” have this software as well, and explain my case?

So, as someone who works for an MSP that specializes in a certain vendors products, it’s maybe worth checking out the websites of who may be your competitors. They love to put their clients names on their websites. This should help you at least start building a list of companies to target (LinkedIn is heavily used by sales peoples these days).