Hi,
We have received some reports that the KB2956128 caused some issues, but it's the first time I've seen this symptom.
As you mentioned removing this kb didn't solve the problem, I still doubt whether the issue is related to this kb.
Have you made any change on Exchange recently? You can expect to see the prompt under the following condition:
If the RPCClientAccessServer property changes.
-Cross AD site mailbox moves may trigger this, as each AD site may have a different RPC Client Access Array.
-If you are not using a CAS Array, if the RPC endpoint changes after a mailbox move. An example of this is when a user on the source database has a
specific CAS as its RPC endpoint, and the destination of the mailbox move has a different CAS specified as its RPC endpoint.
As for the message "Your Administrator has made a change and requires you to restart Outlook", you can find more information and conditions in this blog below, check if it is helpful to you:
http://blogs.technet.com/b/vytas/archive/2014/11/12/your-administrator-has-made-a-change-and-requires-you-to-restart-outlook.aspx
You have the option to completely suppress the dialog:
Uncheck the option Show Microsoft Exchange Messages from the Outlook icon on taskbar, and test the behavior.
I hope this is helpful.
Regards,
Melon Chen
Forum Support