Sounds like Capita have made a mistake or two. Why, if the payment in November failed, did they not contact you then? Why no follow up letter in, say, February? Why has it taken 10 months to chase this. Letters sent in December just get caught up in the Christmas mail. Although I bank on-line, I always keep hard copies of bank statements sent to me for at least a year.
Must admit I have a vested interest in saying they should never have taken the work away from Post Offices. Then you would have had a receipt, as well as the Licence.