Sometimes when you add a contact through you're phone, you're accidentally adding it only to your phone, that is: locally. You may also accidentally be adding it to a different service altogether, such as iCloud.
One way to resolve this is to verify you've selected your zMailCloud/Cloudiance account as your default account, and another way is to check, and change the Contact Group settings.
- Launch the Phone app → Contacts tab.
- Now, tap on Groups at the top left corner.
- Now you can select which groups of contacts you want to see... so you can see which of your contacts are stored in each available way. To ensure best performance without any conflicts or confusion, you should only be adding contacts to your zMailCloud Cloudiance account, and only be viewing them.