Seconding this as something to check (on RHEL it's your "ca-certificates" RPM). Even if you're hitting somewhere "big" you wouldn't think would be using a free cert service because we had someone at $work start getting gripes from wget from the NY FED's site.

Thanks hippo - I had forgotten about the old DST Root certificate issue...

It gave me an avenue to explore but alas, that's not it.

To test I have edited the .htaccess so that it does not enforce HTTPS. Then I have changed the code slightly to remove the HTTPS:

my $availability;
my $response = LWP::Simple::getstore("http://$ENV{'HTTP_HOST'}/cgi-bin
+/booking.pl?command=check&st=$data{'st'}&ed=$data{'ed'}&force=$data{'
+force'}", $availability);
print qq[("http://$ENV{'HTTP_HOST'}/cgi-bin/booking.pl?command=check&s
+t=$data{'st'}&ed=$data{'ed'}&force=$data{'force'}")\n];
print "->$availability<-\n";
print "$response\n";
[download]

Any other ideas of anything I can try to attempt to debug the issue?

You'll have to update the CA store on the server - check the version of Mozilla::CA installed.

It seems you may be right after all hippo!

Is updating the CA store on the server something I can do on shared hosting or do I have to get the server admins to do it? I am able to install new certificates and historically I have had to until, earlier this year, they arranged for Lets Encrypt to automagically renew them.

The Mozilla::CA version is 20120823
I assume that's a date - a very old date!

UPDATE:
I've answered my own question - I can sort of update the CA store...

cPanel has two places for modules. Server wide modules and user level modules. I can, and have, done the update at a user level. To use this version instead of the server wide module I have to have use cPanelUserConfig; before I use any modules that rely on the CA store being up to date.

Is updating the CA store on the server something I can do on shared hosting

It probably depends on the host. My shared hosting had 20130114 installed; when I used their interface to install Mozilla::CA, it now reports 20211001.

Please note that the Lets Encrypt certificates that are automagically renewed are the certificates that allow people to securely connect to your shared host under your domain name(s). That's separate from the CA store on the server, which is the list of certificates that your perl scripts will use to determine if a machine they connect to have a valid certificate or not.

It probably depends on the host

See my update to the earlier node

lease note that the Lets Encrypt certificates that are automagically renewed are the certificates that allow people to securely connect to your shared host under your domain name(s). That's separate from the CA store on the server, which is the list of certificates that your perl scripts will use to determine if a machine they connect to have a valid certificate or not.

I hadn't realised that when the problem first appeared. I had sort of worked it out but it is certainly helpful that you explicitly pointed it out. Many thanks.