Hi, I also have this issue and from what I can see on my W8.1-64 fully patched system this error can also be caused by a DNS query taking to long or returning a null result.
The reason I say this is that I have been playing with bind from isc.org and when I set 127.0.0.1 as the specific DNS server for the network card using IPV4 I always get this error. If I leave it set to return the DNS server from the DHCP query to the router it always seem to work.
The router is on 100% of the time and the store license error only occurs when the computer is booted as I don't leave it on all the time. Once the error has occurred it seems there is no way to get the store to function, at least I have not found a way yet - any ideas?
It would also seem that there is only one attempt and if that fails so be it.
There are also other things I see in the event log that fail because the start-up of bind and its ability to resolve requests takes longer that the other services are prepared to wait. This is potentially due to getting DNSSEC sorted out and if EDNS is not enabled, both would seem to cause a longer start-up time.
However once bind is started it resolves everything perfectly.
I would be interested to hear anyone else's thoughts on this. It may be they are on a slow link to the internet or have issues with the performance etc. In my case my link runs these speeds up/down 19999 / 77047 Mbps, so I think what I have said above holds some truth.