This is one of those "20/20 hindsight is a wonderful thing" posts.
The basic issue is that Visio and Project aren't really part of Office, and should probably be uninstalled before you upgrade the main Office Suite - don't rely on their installers to properly clean them out.
I didn't do this, and had the following symptoms floating around:
Visio 2007 and Project 2007 were both still listed in my All Programs menu, with a tool tip "Installs on first use".
I imagine that at somepoint after upgrading Visio 2007 to 2010, I typed Visio<enter> into my start menu, and Visio 2007 reinstalled itself. I then opened Visio 2010, and that reconfigured itself through an installer. I uninstalled Visio 2007 again from the "Programs and Features" control panel, deleted the links, and the files in C:\Windows\Installers\ that they were pointing at.
Message: Library not registered.
Running the Repair tool (Programs and Features, Office 2010, Change and select "Repair") and restarting my machine seems to have fixed the issue nicely.
I hope this helps somebody else, and saves them the hour or so of confusion it's caused me.
Filed under: Fixes