I faced this situation in the past. I found many scripts in order to reset the database, but not ALL the tables of the database. The scripts I found missed to reset one important thing: credit memos.
To solve this issue, I had to take a closer look at the Magento database structure and guess where the credit memo info was stored. The result is this small script, which will reset your credit memos, basically deleting them all:
SET FOREIGN_KEY_CHECKS=0;
TRUNCATE `sales_flat_creditmemo`;
TRUNCATE `sales_flat_creditmemo_grid`;
TRUNCATE `sales_flat_creditmemo_comment`;
TRUNCATE `sales_flat_creditmemo_item`;
ALTER TABLE `sales_flat_creditmemo` AUTO_INCREMENT=1;
ALTER TABLE `sales_flat_creditmemo_grid` AUTO_INCREMENT=1;
ALTER TABLE `sales_flat_creditmemo_comment` AUTO_INCREMENT=1;
ALTER TABLE `sales_flat_creditmemo_item` AUTO_INCREMENT=1;
Of course, your tables might have some sort of prefix. In that case, just change the database table names accordingly.
Hope this is helpful for you!