If the Bank is a Nationalisead bank, first file RTI Application seeking for certified copy of paid cheque, with RTI fee of Rs.10/- payable to that Bank through IPO.
If it is a private sector bank, issue notice under CPA, as an affected party seeking certified copy of the cheque.
Appeal under RTI comes into picture, only if you have paid RTI Fee and your application is under RTI.
Further both at RBI and Bank's level there is Complaint portal/ or section in Bank's website and complain in on line portal, make a complaint to Branch also, personally handover the same to the Bank, get the dated acknowledgment showing the complaint no. in the register.
Wait for 40days from date of all this correspondence and make a complaint to Banking Ombudsman (address must be displayed in notice board by each and every bank branch) or District Consumer Forum, which ever is convenient to you.
(There is meaning in Bank refusing the information, as you are seeking copy of cheque issued by some others, which amounts to third party information/property. You have to specifically request to issue such certified copy only if your name appears on the cheque as payee, as drawer is not having any right on cheque, after it's issue/giving physical possession to payee. It appears that either you have not explained the fact or Bank official is having a wrong impression that it is a third party informtion. If the cheque is drawn in your name as payee, the rights of drawer extinguished and it is not a personal information at any stretch of imagination. Further larger public interest is also involved as a fraud is suspected and when payee himself is confirming that he has not received payment. So your application /complaint should confirm that it appears that the cheque was drawn in your name, and you have never received such payment and a fraud is suspected. You can also seek information on mode of payment, and name of payee or payee's Bank in your RTI)