Just when you thought Google couldn't make their interface any more confusing, I got tripped up, couldn't find anything useful by searching Google and had to work it out myself. Not the pinnacle of usability!
I wanted to delete someone's secondary email address, which was actually an alias that was added to the user to continue to receive an ex-employees emails. She didn't want them any more.
Opened up the details in Admin screens, and press Edit next to the secondary email address contact information. Deleted the email address, pressed Update User, it all looks happy but behold, the email is still listed as a secondary email address.
The problem? You first have to delete the alias for the user and press Save. Then you can edit the contact information, remove the email address and it stays removed!