UWP Deployment Error after deploying to store - Windows 10

Since deploying my UWP app for windows 10 in the store (beta & private), I can no longer deploy it to my phone (ARM), Tablet Simulator (x86) and my local machine (Surface Pro 3) for testing.

I've rebooted both my phone and my SP3 but I'm still getting the same error:

Severity    Code    Description Project File    Line    Suppression State
Error       Error : DEP0001 : Unexpected Error: Install failed.
Please contact your software vendor. (Exception from HRESULT: 0x80073CF9)   

I've googled the error and found this article:

https://msdn.microsoft.com/en-us/library/windows/desktop/hh973484(v=vs.85).aspx

According to this article/page, I should check the AppXDeployment-Server log

ERROR_INSTALL_FAILED 0x80073CF9 
Package install failed. Contact the software vendor.

Check the AppXDeployment-Server event log for more info.

I did, but I didn't find anything useful. I've just tried to re-deploy to my phone and no entries were added. The last entry in this log was from 52 minutes prior to now. I've also checked the AppXDeployment log and nothing either!

Could it be related to visual studio having generated a new certificate? I'm not sure to be honest.

When I try to deploy it on the Simulator or the Local Machine, I get a different error:

Severity    Code    Description Project File    Line    Suppression State
Error       Error : DEP0700 : Registration of the app failed. An
internal error occurred with error 0x80073D05. See
http://go.microsoft.com/fwlink/?LinkId=235160 for help diagnosing app
deployment issues. (0x80073cf6)         

I managed to resolve this issue after finding this article:

Error: DEP0700: Registration of the app failed. An internal error occurred

And it's now working again on my Local Machine & my Simulator but I've never had to do this before until now.

I think the above might related to the fact that I try to repair my VS 2015 and it messed things up as I noticed that my Target Version & Min Version were changed from 10586 to 10240.

I decided to re-install the Windows Software Development Kit for both 10586 and 26624 but the problem remains. I still can't deploy directly on my device (ARM).

Any help would be greatly appreciated and the last thing I want to do is having to wipe my machine!

Thanks.

Thierry

UPDATE-1:

I've just created a new blank UWP and this still works which would lead you to believe that the problem is not with the files on the machine, visual studio or my phone. By the looks of it, something is messed up in my UWP project but what???

I've also noticed that all my emulators for 10240 are all missing, not that I need them but I thought I'd mention it anyway.

UPDATE-2:

Here is the output log, in case it helps:

1>------ Build started: Project: MyApp, Configuration: Debug ARM ------
1>  MyApp -> C:\Windows Universal\MyApp\MyApp\bin\ARM\Debug\MyApp.exe
1>  Starting .NET Native compilation
1>  Processing application code
1>C:\Windows Universal\MyApp\MyApp\Resources.System.Linq.Expressions.rd.
  xml(35): warning : Method 'CreateLambda' 
  within 'System.Linq.Expressions.Expression' could not be found.
1>C:\Windows Universal\MyApp\MyApp\Resources.System.Linq.Expressions.rd.
  xml(91): warning : Method 'ParameterIsAssignable'
  within 'System.Linq.Expressions.Expression' could not be found.
1>  Computing application closure and generating interop code
1>  Generating serialization code
1>  Compiling interop code
1>  Cleaning up unreferenced code
1>  Generating native code
1>  Generating fixups for native code
2>------ Deploy started: Project: MyApp, Configuration: Debug ARM ------
2>Deploying to Phone Internal Storage...
2>Updating the layout...
2>Copying files: Total 11 mb to layout...
2>Checking whether required frameworks are installed...
2>Registering the application to run from layout...
2>Error : DEP0001 : Unexpected Error: Install failed. Please contact 
  your software vendor. (Exception from HRESULT: 0x80073CF9)

I've compared both the solution and project files for the new app (which works) and my actual app and can't see anything critical. There were differences, but when removing them one by one, it made no difference in the outcome.

I'm doing the same now via the IDE and just spotted that the Compile with the .NET Navite Tool Chain was ticked in my new app and wasn't in my actual app. I've selected it now, but still no luck. The only difference is that it's seems to be taking much longer to deploy before throwing the reported error.

UPDATE-3:

Note that the "Compile with the .NET Native Tool Chain" was because one project as in Release mode while the other one was in Debug mode but it had no effect on the issue.

I tried resetting the certificate to be set to the temporary one, but again, no change!

There was no differences between the options in the Project Properties. I did find a solution and what a waste of my time!! I'll post it in a second as the answer but it could be one of many!

In order to resolve this problem, wait for it...., all I had to do was remove the old instance of my app that was installed on my phone.

As mentioned, in my update, I cannot believe this was the root of all my problems! What a poor error. I still don't understand why this resolved it as you would assume it would have updated the app as it did many times in the past.

I had thought about removing it at an earlier stage but I was reluctant doing so as I wasn't sure I would be able to re-install it until this problem was solved and I use the app on a daily basis, but having ran out of options, I decided to do so and the second I did, it installed the new version immediately and I was able to debug directly via the IDE as well.

What a pain and what a waste of time but hey, problem is solved which is the main thing!

Hope this helps others facing the same problem.