Algo que eu sempre usei no passado é o HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Session Manager\
PendingFileRenameOperations
valor do registro. Se não estiver vazio, você está aguardando uma reinicialização. Observe que o valor do registro não deve existir, a menos que você esteja aguardando uma reinicialização. É apagado após a reinicialização. Então, se você não vê, é por isso.
Editar: também jogue essa chave na mistura:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Updates\UpdateExeVolatile
Essas duas chaves juntas devem informar se uma reinicialização está pendente ou não.
Verifique este artigo da Microsoft - embora o artigo seja sobre o Exchange, ele claramente menciona como a verificação desses dois valores do Registro é como o Exchange sabe se uma reinicialização está pendente ou não: link
Editar 29 de outubro de 2014: A Microsoft lançou um novo recurso Desired State Configuration chamado xPendingReboot que fará um bom trabalho em descobrir se o seu sistema está pendente reinicialize ou não. Ele faz isso observando a seguinte lista de chaves do Registro:
$ComponentBasedServicing = (Get-ChildItem 'hklm:SOFTWARE\Microsoft\Windows\CurrentVersion\Component Based Servicing\').Name.Split("\") -contains "RebootPending"
$WindowsUpdate = (Get-ChildItem 'hklm:SOFTWARE\Microsoft\Windows\CurrentVersion\WindowsUpdate\Auto Update\').Name.Split("\") -contains "RebootRequired"
$PendingFileRename = (Get-ItemProperty 'hklm:\SYSTEM\CurrentControlSet\Control\Session Manager\').PendingFileRenameOperations.Length -gt 0
$ActiveComputerName = (Get-ItemProperty 'hklm:\SYSTEM\CurrentControlSet\Control\ComputerName\ActiveComputerName').ComputerName
$PendingComputerName = (Get-ItemProperty 'hklm:\SYSTEM\CurrentControlSet\Control\ComputerName\ComputerName').ComputerName
$PendingComputerRename = $ActiveComputerName -ne $PendingComputerName