I cannot reproduce this problem ...

The only address that cannot be deleted is the Primary Address ...

To rule out some type of template issue, if you switch to the Classic Template, does the delete work on the addresses?