After a long time having this issue on Xamarin.Android with Visual Studio 2017, I found a workaround in case anyone finds him or herself in the same situation.

It looks like Xamarin.Android uses MSBuild 4 and as Visual Studio 2017 uses MSBuild 15, it wasn't finding the assemblies the Xamarin.Android build toolchain requires, although you can still use MSBuild 15 but it needs Microsoft.Build.Framework.v4.

Solution

The solution is simple, simply add a reference to MSBuild 15 in References -> Add Reference... -> Framework.
The next step is adding a reference to Microsoft.Build.Framework.v4. You can find this assembly in the GAC.

Even though it solves the issue, it creates another issue if you have a CI process, since now you'll have to check-in these dlls. At least the Microsoft.Build.Framework, since I think MSBuild comes with Visual Studio needed to compile the project or solution.