The rule is that if an App ID that has ever been submitted with an App to the store, it cannot be deleted (even if it was not accepted). App IDs that have not yet been used to submit apps can be freely deleted.
Checkout this thread on Apple Developer Forums (You’ll need to be logged in to view):
https://devforums.apple.com/message/801353