Force uninstall of Visual Studio
Microsoft started to address the issue in late 2015 by releasing VisualStudioUninstaller.
They abandoned the solution for a while; however work has begun again as of April 2016.
There has finally been an official release for this uninstaller in April 2016 which is described as being "designed to cleanup/scorch all Preview/RC/RTM releases of Visual Studio 2013, Visual Studio 2015 and Visual Studio vNext".
I was running in to the same issue, but have just managed a full uninstall by means of trusty old CMD:
D:\vs_ultimate.exe /uninstall /force
Where D: is the location of your installation media (mounted iso, etc).
You could also pass /passive (no user input required - just progress displayed) or /quiet to the above command line.
EDIT: Adding link below to MSDN article mentioning that this forcibly removes ALL installed components.
http://blogs.msdn.com/b/heaths/archive/2015/07/17/removing-visual-studio-components-left-behind-after-an-uninstall.aspx
Also, to ensure link rot doesn't invalidate this, adding brief text below from original article.
Starting with Visual Studio 2013, you can forcibly remove almost all components. A few core components – like the .NET Framework and VC runtimes – are left behind because of their ubiquity, though you can remove those separately from Programs and Features if you really want.
Warning: This will remove all components regardless of whether other products require them. This may cause other products to function incorrectly or not function at all.
Good luck!