When it "locks up", can you still hit the CTRL-ALT-DEL keys? If so, can you then open the "Task Manager"?
My Dad got some bug like that not too long ago. Every time he opened his web browser (IE11) he would get that message. Then couldn't close it or do anything with it.
I did the C-A-D deal, brought up Task Manager and found that it was just an IE instance running. I Ended Task on it and it went away and could resume with the session.
I ran the malewarebytes and found some things, but it turned out that it also set his 'home page' to be that website that showed the message from "Microsoft".
It doesn't sound exactly like the same deal, but thought I'd just toss that out there to try.
Good luck!
Mitch