No matter what I did, the "Previous Versions" tab for every file said "There are no previous versions available". System Restore was turned on, and both the GUI and vssadmin said that there were restore points. I was able to access old versions of files using syntax like "\\?\GLOBALROOT\Device\HarddiskVolumeShadowCopy1\config.sys". I was even able to access old versions via the "Previous Versions" tab when I accessed files via shared folders (eg. "\\computername\public").
The solution was enabling administrative shares (such as C$). In the past I set the dword at "HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\services\LanmanServer\Parameters\AutoShareWks" to 0, which disabled them. I simply deleted that registry entry and restarted. (Note that even though Vista is a workstation OS, the registry entry is under LanmanServer.)
I wasted way too much time on this. I hate when something fails and there is no indication what went wrong. (I imagine something was trying to connect to C$ and it was failing, but that error was never reported.) This is actually my main complaint about Windows.
All this also applies to Windows 7.