Deleted product information persisting

I am getting an error when attempting to add a new product: "A Product named 1234 already exists."

I had added a product with the same properties before, along with discounts associated with the product. I then deleted the product and the discounts associated with it. The product can no longer be found in the catalog manager by searching or browsing. I've also looked through the productcatalog database, and found no entries for that product. The discounts have remained in the system and are visible in the Marketing Manager as Deleted Items.

What do I need to do to add this product again?

Thanks :)

[643 byte] By [MichaelMcBryde] at [2007-12-28]