I recently attended a SharePoint developer training class led by Todd Bleeker, SharePoint MVP.  Todd is a great instructor, and one of his comments during the week seemed to ring true for anyone with experience with SharePoint.  He related SharePoint development to playing Pac-Man.  You eat a dot (develop a little bit), then go test, and repeat this process over and over and over again.  He attributed this in part to a lack of documentation regarding SharePoint extensibility.

I would say that this applies as well to Visual Studio extensibility.  The documentation is lacking at best, and I've spent a lot of time in Google and Reflector recently trying to put the pieces together.  And I've eaten another dot.

The answer to my VsTemplatePaths problem was painfully easy, yet just plain painful to find.  The answer came when I ended up diffing my project with an earlier project that used the Visual Studio Integration Package.  I was missing the following nodes in my project file:

    <TargetRegistryRoot>Software\Microsoft\VisualStudio\8.0Exp</TargetRegistryRoot>
    <VsTemplateLanguage>CSharp</VsTemplateLanguage>

Yup, that was the whole problem, and now my project correctly builds.  An astute reader validated my answer as well, thanks Alex!  He also mentioned that the deployment path gets built from the two variables above.  Diving into Microsoft.VsSDK.Build.Tasks.dll in Reflector, specifically the Execute method in the VsTemplatePaths class, that is in in fact correct.  This results in:

HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\VisualStudio\8.0Exp\VSTemplate\Project\UserFolder

    Path.Combine("C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\ProjectTemplatesExp", "CSharp);

 HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\VisualStudio\8.0Exp\VSTemplate\Item\UserFolder

    Path.Combine("C:\Program Files\Microsoft Visual Studio 8\Common7\IDE\ItemTemplatesExp", "CSharp");