Organizing and accessing contact information in Outlook.com
>> do a hard reset of your Windows Phone for a completely fresh start.
I started by ditching my WP 6 months ago :)
And it's not related to the phone sync either (WP or other) as the problem happened even when I unlinked my phone. It's on server side.
>> ditch your current outlook.com account,
Does this mean changing the email address? And what about all my Xbox achievements and gametag? Not an option, sorry.