I had a user come to me with this problem who uses a child account, and was then able to replicate it on my own personal Zimbra server at home.
If you're using a child account, it seems "Add new contacts to Emailed Contacts" does not work. Contacts are not added to either the parent or child "Emailed Contacts" address book.
When trying myself, it stopped working when I set up a test child account, and resumed working when I removed it.
My own server is 7.1.3_GA_3346, and the site one in question is 7.1.4_GA_2555, both Open Source editions.
Couldn't find a matching bug...
Anyone else experienced or know about this?