Ok, nailed it. There were two problems:

1. I was correct in that you were feeding the wrong key, but incorrect about why.
   
   It turns out you need to set -literal_key => 1 because otherwise, as per Crypt::CBC, it helpfully uses a hash of the key you provide rather than the key itself.
   
   And then you also need to set -keysize => 16, because otherwise it complains about you not providing a 32-byte key (and apparently once you set keysize, setting -blocksize => ... makes no difference at all).
   
   
2. You were getting the plaintext wrong. Going back to the source (page 37 of FORM_Integration_and_Protocol_Guidelines_130515.pdf which I assume is what you're working from), which I'll quote

   VendorTxCode=TxCode-1310917599-223087284&Amount=36.95&Currency=GBP&Des
   +cription=description&CustomerName=Fname
   Surname&CustomerEMail=customer@example.com&BillingSurname=Surname&Bill
   +ingFirstnames=Fname&BillingAddress1=BillAddress Line
   1&BillingCity=BillCity&BillingPostCode=W1A
   1BL&BillingCountry=GB&BillingPhone=447933000000&DeliveryFirstnames=Fna
   +me&DeliverySurname=Surname&DeliveryAddress1=BillAddress
   Line 1&DeliveryCity=BillCity&DeliveryPostCode=W1A
   1BL&DeliveryCountry=GB&DeliveryPhone=447933000000&SuccessURL=https://e
   +xample.com/success&FailureURL=https://example.com/failur
   e
   [download]

   and the question you want to ask when you see shit like this is why are the line-breaks where they are.
   
   Sometimes it's because it's running all the way to the end of the (however many characters wide) space provided, as is clearly happening with the word "failure" on the last line, but other places it's clearly doing something else, and the other thing that it's doing is breaking at places where there's a space available to break at because whatever idiot composed this document just did a regular paragraph fill, which helpfully left the spaces at the ends of the lines where you can't seem them unless you drag the mouse over the text in the original .pdf and watch what happens with the highlighting (and then Adobe or Windows helpfully strips out the trailing spaces when you try to paste to another application).
   
   In particular, every place where the postcode "W1A1BL" appeared, it's actually supposed to be "W1A 1BL" (and if the last time I'd been to Britain were more recently than 1997, I might have noticed this sooner).
   
   Also "CustomerName=Fname Surname", and so on. Putting it all together we get

   my $user_string = 'VendorTxCode=TxCode-1310917599-223087284&Amount=36.
   +95&Currency=GBP&Description=description&CustomerName=Fname Surname&Cu
   +stomerEMail=customer@example.com&BillingSurname=Surname&BillingFirstn
   +ames=Fname&BillingAddress1=BillAddress Line 1&BillingCity=BillCity&Bi
   +llingPostCode=W1A 1BL&BillingCountry=GB&BillingPhone=447933000000&Del
   +iveryFirstnames=Fname&DeliverySurname=Surname&DeliveryAddress1=BillAd
   +dress Line 1&DeliveryCity=BillCity&DeliveryPostCode=W1A 1BL&DeliveryC
   +ountry=GB&DeliveryPhone=447933000000&SuccessURL=https://example.com/s
   +uccess&FailureURL=https://example.com/failure';
   [download]

With those two changes, I'm getting the right ciphertext. (It took a bit of doing but with block ciphers used in one of the chaining modes, if you're getting something that's correct up to a point, that tells you which block your mistake is in and you go from there...)

(and apparently, yes, they really are using 16-byte keys consisting entirely of bytes in the hex-digit range, which effectively means they're using 8-byte keys. Just for grins, I looked at their sample .php source and there's no provision for providing arbitrary keys and packing them. These people are screaming to get hacked.)