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]

This still behaves the same. $availability is empty and $response is 500.
I have checked that pasting the URL into a browser still works and doesn't change to HTTPS.

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