Hello Adam,
Another technique might be to consume events generated by the Microsoft-Windows-Win32k provider in real-time, using a keyword filter such as UIUnresponsiveness or AutoRotation to reduce the number of irrelevant events reported. There are "Start" and "Stop" events for "ForegroundWindowFullScreen":
Update:
Another option is to receive WM_SHELLHOOKMESSAGE messages (either by calling RegisterShellHookWindow or by hooking WH_SHELL messages); the HSHELL_ values for entering/leaving full screen appear to be 53/54 (undocumented values).
Gary