Even though i am just adding a received call it asked me to store in either of the 2 synced contacts. Do you have microsoft account and hotmail account linked together? i first set up the hotmail account and it asked back then to include it with micrisoft account i think.
When i have a new number - click on it .. see profile and history of unknown caller. select the disc on the bottom bar.. see all contacts.. hit the plus on bottom bar and get a scree ncalled "create contact in" with the select option gmail or hotmail. select hotmail and can select which kind of telephone number this is. Checking outlook.com after that - the contact is there.
if you check account settings - do you have contacts checked on your google account?