Questo errore capita quando si cerca di deploiare una solution (*.wsp) tramite Visual Studio in una farm SharePoint con più server (Multi Server Farm).
Error occurred in deployment step 'Activate Features': Feature with Id 'xxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx' is not installed in this farm, and cannot be added to this scope.
Nel mio caso si trattava di una farm SharePoint 2013 con 4 server e Visual Studio 2012.

Questo perché Visual Studio implementa internamente solo il local deploiment.

La soluzione è fare il deploy a mano tramite powershell e/o central administration.