This is a perfect example of why the Credit Card "chargeback" process exists!
Firstly, check your credit (or debit) card statement to confirm that it was actually the hotel that charged you and not someone acting on their behalf.
The first step of obtaining a charge-back is to contact whoever charged you and discuss the charge with them. This is best done via email so that you will have proof of the discussion. Presuming it was the hotel that charged you, then it sounds like you have already done this.
Next, contact your credit card company and "dispute" the charge. They will ask for any proof you have that the charge is not legitimate - in which case you can provide the details you have around the cancellation, and in particular the fact that the hotel claims they did not charge you.
At this point the credit card company will investigate the charge (including contacting the hotel to get their side of the story). Unless the hotel is able to prove the charge is legitimate - which is unlikely in this case - then it will be reversed. It is possible that the credit card company will credit the amount to you immediately whilst they investigate, but if not then you should plan to pay any outstanding bills in order to avoid penalties.