How does Windows XP Task Manager know when a program is not responding?

When task manager says "Not responding" does not actually mean that
the application is dead. You will notice this behavior when a program
starts doing some intensive processing and hogs lot of CPU and does
not yield. At that point, you will notice that TM will display "Not
reponding message". Usually the culprits are the contained components
in the main process. For example if you have a rogue ActiveX control
hosted in Internet Explorer and that component goes into runaway
condition, then TM will say that IE is not reposnding.

TM usually makes decision based on WM_IDLE message. If a process is
not yielding to this message or not reponding to the message TM puts
up that message. Usually TM sends WM_GETICON message to the process.
If it does not return then.... "Not responding"