Your bank are incorrect in what they are saying to you. Assuming it is an Irish clearing bank, they are obliged to hold an image under the industry clearing rules for 6 years. Images are captured centrally, usually by a 3rd party supplier and not at the branch. Ask your branch to contact their clearing department for a copy, it will take a few days
Bear in mind that if you have been debited the wrong amount, likelihood is that the payee has been credited the wrong amount. That should not be your problem, tell your bank to put you right, it is up to them to secure the overpayment back from the payee and their bank if required.
You have no entitlement to get the actual cheque back and most banks destroy the cheques after 2-3 years. Solicitors do get their physical cheques back but that is due to their interpretation of various Solicitors Acts which require them to store a copy of their records and they deem cheques to be a record. Banks disagree with this and have challenged it. Legislation has recently been passed in the UK to formally remove this requirement from 2017 onwards, that will also apply to Northern Ireland and the Central Bank are considering similar legislation for here.