Generally when the problem appears to be that the Windows message queue mechanism is too slow, that is usually not the case at all.
It can only deliver you the next message when you request it, and you normally only request it when you are finished dealing with the current message. So basically your own slow message processing slows down the receipt of further messages.
One mistake I've come across when processing Windows messages is when you only allow at most one Windows message to be processed each time around your main loop, seemingly giving maximum time to the rest of your drawing code. In reality what happens is that this slows the program down horribly. You should endeavour to process ideally all messages before doing any other stuff in your main loop. Although this may be counter-intuitive, it actually makes a world of difference. Give Windows more attention and promptly process its messages, and your program's performance will be greatly rewarded.
Those are not interrupts and no you do not need a mutex there. In fact the term "interrupts" doesn't have much applicability at all in a Windows program. The terms that you need to be familiar with are synchronous / asynchronous, blocking / non-blocking, or single-threaded / multi-threaded.
You can confirm this for yourself by placing a breakpoint within the HandleInterrupt function, and when the breakpoint is hit, examine the Call Stack window. When you can look back through the call stack of the same thread and find the original GetMessage or PeekMessage call, then what your application is doing is entirely synchronous, or blocking.