But PPM tells me that Crypt::SSLeay is indeed installed. Do I have to USE it explicitly or something?

Give it a shot :-)

The documentation says that you do not need to explicity use it (or at least the example does not use it). Perhaps reinstall and check for errors.

Updated with links.