how do I know that the "unusual" package is available on that server - or on *any* server if truth be told?

For standalone scripts and apps, the "modern" approach (taken from other systems like Ruby and Python) is to bundle such scripts with a cpanfile that describes the dependencies that your scripts will need. This way, you do not have to query whether such a dependency is on your destination server or not; you declare such a dependency instead, so that tools like cpanm can install those for you.

In addtion, should you need to depend on exact versions of a particular module, tools like Carton will read the cpanfile to get that particular version installed for your usage.