My current workaround I've come up with after some time is to change the display name of the extension package in the source.extension.vsixmanifest file:
<Metadata>
...
<DisplayName>Change this name to sth else and press F5</DisplayName>
...
</Metadata>
Nothing else needs to be changed (unfortunately reversion to old name still fires this error, but at least developing and debugging can be continued).
UPDATE:
I've checked the windows registry for such problematic name, and found following PendingDeletions
key:
HKEY_USERS\S-1-5-21-1832937852-2116575123-337272265-599953\Software\Microsoft\VisualStudio\11.0Exp\ExtensionManager\PendingDeletions
Under this key there is value pointing at my extension I've previously uninstalled (while being in the debug mode):
C:\USERS\G_159\APPDATA\LOCAL\MICROSOFT\VISUALSTUDIO\11.0EXP\EXTENSIONS\JAROSLAW WALISZKO\MYEXTENSION\1.0\
Removal of this entry fixes that case.