It's probably running out of entropy. If windows is anything like Linux, it will use certain random events like mouse movements, keystrokes, boot time etc. to generate randomness.
But yes, I have seen a similar case involving linux /dev/random - the user reported that outgoing emails were sometimes delayed for hours and that moving a mouse over a VNC window would sometimes speed it up. I did not believe that at first, but it was exim4 running out of entropy when generating TLS session keys. Worse, it was on a VPS with about 20 exim4 processes competing for the entropy.