After reinstalling VS 2005 and reinstalling WSE 3.0 I couldn't find the WSE Settings tool in my context menu. Digging a little bit further soon made me realize that the add-in wasn't even showing up in the Add-In Manager. By a coincidence, searching for another WSE 3 problem I found a command that would re-register the WSE Addin:
devenv.exe /resetaddin WseSettings.Connect /command File.Exit