How to check that a known Windows Vulnerability has been patched?

Running SystemInfo against your server (systeminfo /s $SERVER) should also list installed hotfixes.

Hotfix(s): 333 Hotfix(s) Installed.
[161]: IDNMitigationAPIs - Update
[162]: NLSDownlevelMapping - Update
[163]: KB929399
[164]: KB952069_WM9
[165]: KB968816_WM9
[166]: KB973540_WM9L
[167]: KB936782_WMP11

WMIC can list installed hotfixes:

C:\>wmic qfe get hotfixid, installedon
HotFixID   InstalledOn
KB2605658  11/30/2011
KB2608610  9/1/2011
KB2608612  9/26/2011
KB2614194  9/26/2011
...(more)...

It can also search for a specific hotfix. Here I show two searches - one successful, one unsuccessful:

C:\>wmic qfe where (hotfixid = 'KB2608610') get hotfixid, installedon
HotFixID   InstalledOn
KB2608610  9/1/2011

C:\>wmic qfe where (hotfixid = 'nosuch') get hotfixid, installedon
No Instance(s) Available.

I run PSinfo -h against the server to show installed hotfixes.

Another alternative if you can't use pstools and find yourself stuck with native Winder tools:

reg query hklm\software\microsoft\windows\currentversion\uninstall /s | findstr "KB[0-9].*" > %TEMP%\Installed.txt & notepad %TEMP%\Installed.txt

Also for checking vulnerabilities on subsystems that you might not know about on the system, the Microsoft Baseline Security Analayzer is a fairly useful tool. It's not always the ones you know about that get you, sometimes there are oddball things installed that aren't scanned or serviced by WSUS or Microsoft Update that can remain unpatched or unmitigated for the life of the system.