When a plan is deleted it isn't removed from Bamboo.
The plan is marked for deletion and doesn't appear in the UI.

If a customer re-creates the plan with same Plan Key, then he gets an error saying the plan key already exists - we should throw a more meaningful error.