WM_QUERYENDSESSION is sent to all top level windows on the desktop in the closing session. However since your service usually runs in a different session, you normally won't get the notification. Before Vista you could enable interaction with desktop to share the desktop with the user on session 0, but you won't get the message sent to you if the logging off happens in another session. After XP, you won't get messages from user sessions due to session 0 isolation.
To notify your service of this message, you need to run an agent process in each session (that is, register to auto start when the user log in via start menu shortcut or registry) and listen to WM_QUERYENDSESSION (in .Net terms, run a message pump like Application.Run in Windows Forms and subscribe to SystemEvents.SessionEnding), then gather session information and send the notification to your service through inter-process communication methods like named pipe (if you use WCF, use NetNamedPipeBinding). If you want to get the current session, use WTSQuerySessionInformation (or in .Net terms, Process.GetCurrentProcess().SessionId)
The OnSessionChange method is called after the user has logged off. Same for SENS's log off event, so those two are too late for you.