When I go to Preferences -> Layout to change the hotkeys when the issue is happening, I'm unable to set it to the original values. I can press Ctrl+Cmd and it shows up in the hotkey input, but the last key doesn't work. This works again after a restart though.
I have "Change Space" set to Ctrl+Cmd+Arrow keys and these always work even when the desktop specific hotkeys don't. I did a little more testing and the problem might be related to the laptop going to sleep? Not sure, but if I unplug the multiple monitor connections to the laptop and plug them back in immediately, the hotkeys still work fine.