Office 2013 Retail deactivating itself

Hello
I have a strange problem where Office is deactivating itself, but only for a small number of users.
I'm absolutely sure their keys are only used once.
Did you see anything like this ?
I get two messages:
Microsoft Office cannot verify the license for this product. You should repair the Office program by using Control Panel.

and

We're sorry. but Word has run into an error that is preventing it from working correctly. Word will need to be closed as a result. Would you like to repair now.

My PCs have limited access to the internet, and they are going on-line through the proxy, but the installation (and activation) was done with internet fully opened / without proxy.

Nothing worked so far. I cannot repair, activate over internet or phone.

I even uninstalled it and reinstalled with completely new, still sealed key, and it happened again after few days.

What is strange is that the reboot will fix it for few days, and then, it will happen again.