I understand a paper cheque ("check" en-US) is essentially a type of legally enforceable contract.
The writing on the cheque essentially says: "I, Mr. Moneybags will pay £500 to Mr. John Smith. I bank with Coutts Bank. My account number is 1234. I have signed this paper. Give this paper to Coutts Bank and they will give you £500 from my account in cash."
(Historically) when Mr. John Smith deposits this cheque with his bank (e.g. Lloyds Bank), then someone at Lloyds bank takes the cheque and then physically drives over to Coutts Bank and presents the cheque. Lloyds Bank can prove that John Smith is a customer of theirs and that they have the right to act on his behalf to collect the money. Coutts agrees and verifies Mr. Moneybags' signature on the cheque and gives the £500 to the Lloyds worker with the expectation they'll put it in John Smith's account. If Mr. Moneybags doesn't have the £500 then Lloyds charges Mr. John Smith £20 for wasting their time driving over to Coutts for nothing.
...at least, I understand that's how things worked prior to inter-bank networks. I understand that now (in countries like the US, UK, Canada, etc) that Lloyds would just make a digital scan of the cheque and essentially just send an e-mail to Coutts and Coutts then verifies that the cheque is authentic from the image alone and if it's valid then tells Lloyds that they can add £500 to John Smiths' account and pinky-swears that they've deducted £500 from Mr. Moneybags' account (though I assume these promises are audited regularly).
So that's how banks do it - but how do Money Service Businesses (aka Cheque Cashing shops) do it?
I imagine that Mr. John Smith would enter an MSB shop and present the cheque to an employee and he also shows some form of biometric ID like a driver's license to prove that he is a John Smith (assuming the cheque didn't add additional identity assertions) - and the MSB then gives him £500 cash and then keeps the cheque.
...but how does the MSB get £500 back from Coutts bank? Unlike actual banks, I don't believe there is a trust-relationship or network established between banks and MSBs - the bank has no way of knowing that an MSB is legally able to collect money on John Smith's behalf. The cheque that the MSB collects still has Mr. John Smith's name on it - not their business name. As cheques are contracts then they must be immutable and cannot be unilaterally altered - and if I turned up at a bank and presented a cheque made out to someone else and swore up-and-down that they should give the money to me instead they'd probably confiscate it and call the police on me.
...so how do MSBs get the money from a cheque they receive when it doesn't have their name on it?