Solution 1:

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!

Solution 2:

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".