Cheque impayé finalement payé et recouvrement

Bonjour a tous

J ai un petit soucis , voila le mois dernier , j ai émis un chèque au magasin leclerc , 2 semaines après ma banque a refuser le payement de ce chèque alors qu'il y avait l argent sur le compte ,bref j ai reposer de l argent sur le compte et j ai appeler leclerc pour les prévenir , ils ont relancer le chèque le 23 septembre qui cette fois a été encaisser sans problème .
Hors ce matin je vais faire mes courses , et arriver a la caisse la caissière me dit que mon chèque ne passe pas .
Ni une ni deux , je rentre chez moi j appel ma banque qui me dit qu il n y a aucun problème , que je ne suis pas interdit au chèques .J appel donc Leclerc qui me fait passer de service en service , puis finalement me donne un 0811 a appeler , qui eux me dise que j ai 45 euros de frais a leur payer pour frais de recouvrement et de courrier , alors que je n es jamais reçu aucun courrier de leur part , et que c est leclerc qui a encaisser le chèque et non une société de recouvrement , donc normalement je ne dois rien a une société de recouvrement .
Sachant qu en plus j ai déjà payer des frais de 50euros (pour un chèque de 61 euros) a la banque de France , et 14euros a ma banque pour l intervention .
Dois je vraiment payer ses 45 euros a la dite société de recouvrement alors que je n es jamais reçu de courrier de leur part et leclerc a encaisser le chèque ?
car en attendant je ne peux émettre de chèque dans tout les leclerc de France ainsi que les magasins cora et d autre magasin avec qui la société de recouvrement travaille .?

Ce qui veux dire qu entre les frais de banques de France , de ma banque j ai payer 64 euros ,plus leur soit disant frais a eux de 45 euros , j aurai payer 3fois mes courses de 61 euros !Pour une malheureuse erreur .
Merci au réponses sérieuses