I am not sure if it's some kind of core-logic(unknown to me) or a bug maybe, but even though I have already deleted a coupon-code rule from "Shopping Cart Price Rules", when I search in the "salesrule_coupon" table the deleted coupon code, it still shows up.
What happens due to the above scenario is that if I try to recreate the coupon-rule with same code, it doesn't allow me to do so and shows below message:
Coupon with the same code already exists.