After using the "remove-appxprovisionedpackage" cmdlets with the -online parameter the start menu for new users still has a number of orphans. Are we doing something wrong when we are trying to remove some of these applications?
You will likely need to apply a customized start menu layout, not just for the de-provisioned apps but also for the "placeholder" icons that would install additional apps from the Windows Store (e.g. the "Candy Crush" scenario). (Disabling the "consumerization" policy doesn't get rid of the placeholder icons.)