I finally found the solution, so I share it in case someone will have the same issue someday.
The problem was that when I uninstalled VS 2015 community for some reason it didn't delete a key in the registery, in VS output I got this exception (but it didn't show every time I tried to create the porject, just sometimes)
Exception MSBuildToolsPath is not specified for the ToolsVersion "14.0" defined at "HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSBuild\ToolsVersions\14.0", or the value specified evaluates to the empty string. (InvalidToolsetDefinitionException):
at Microsoft.Build.BuildEngine.InvalidToolsetDefinitionException.Throw(Exception innerException, String resourceName, Object[] args)
at Microsoft.Build.BuildEngine.ToolsetReader.ReadToolset(PropertyDefinition toolsVersion, BuildPropertyGroup globalProperties, BuildPropertyGroup initialProperties, Boolean accumulateProperties)
at Microsoft.Build.BuildEngine.ToolsetReader.ReadEachToolset(ToolsetCollection toolsets, BuildPropertyGroup globalProperties, BuildPropertyGroup initialProperties, Boolean accumulateProperties)
at Microsoft.Build.BuildEngine.ToolsetReader.ReadToolsets(ToolsetCollection toolsets, BuildPropertyGroup globalProperties, BuildPropertyGroup initialProperties, Boolean accumulateProperties)
at Microsoft.Build.BuildEngine.ToolsetReader.ReadAllToolsets(ToolsetCollection toolsets, ToolsetRegistryReader registryReader, ToolsetConfigurationReader configurationReader, BuildPropertyGroup globalProperties, BuildPropertyGroup initialProperties, ToolsetDefinitionLocations locations)
at Microsoft.Build.BuildEngine.Engine.PopulateToolsetStateMap(ToolsetDefinitionLocations locations)
at Microsoft.Build.BuildEngine.Engine..ctor(Int32 numberOfCpus, Boolean isChildNode, Int32 parentNodeId, String localNodeProviderParameters, BuildPropertyGroup globalProperties, ToolsetDefinitionLocations locations)
at Microsoft.Build.BuildEngine.Engine.get_GlobalEngine()
at Microsoft.VisualStudio.Package.Utilities.InitializeMsBuildEngine(Engine existingEngine, IServiceProvider serviceProvider)
at HedgehogDevelopment.SitecoreProject.VSIP.SitecoreProjectPackage.Initialize()
So all what I had to do was to delete the key in the registery as explained here.
I edit my question as suggested by @Richard Seal
Open registery (regedit)
Navigate to HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\MSBuild (OS 32 bit) or HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\MSBuild (64 bit)
Before you go farther back up this register key (select MSBuild key then file -> export)
Expand ToolsVersions under MSBuild, you should see 14.0 which appears under ToolsVersions but not under MSBuild, delete this key
If you have VS running you should restart it