How to fully uninstall a Windows Store app?

Built-in apps are called provisioned apps. They are scheduled to be installed for each new user that registers on a Windows 8 PC, so you can't uninstall them completely from the Start screen. To do so, you've to use Windows PowerShell command remove-AppxProvisionedPackage, like so:

remove-AppxProvisionedPackage -package Microsoft.BingTravel_1.2.0.145_x64__8wekyb3d8bbwe -online

That would uninstall the Travel app. To remove Bing Map app, the command would be:

remove-AppxProvisionedPackage -package Microsoft.BingMaps_1.2.0.136_x86__8wekyb3d8bbwe -online

Microsoft.BingMaps_1.2.0.136_x86__8wekyb3d8bbwe is the app package name, which basically is the folder that you find in C:\Program Files\WindowsApps.

To uninstall apps installed from the Windows Store, the command is Remove-AppxPackage. It's syntax is as below:

Remove-AppxPackage PackageFullName

Note: Do not add -online parameter at the end of this command. [source]

I had success with the following method. Press Win+X, select Command Prompt (Admin). Run the command

DISM.exe /Online /Remove-ProvisionedAppxPackage /PackageName:Microsoft.BingTravel_1.2.0.145_x64__8wekyb3d8bbwe

Use folder names in the "C:\Program Files\WindowsApps" folder as package names.

Source: http://technet.microsoft.com/en-us/library/hh852635.aspx

To automate this process, I got a list of packages by running "dir /b". Then converted it into a batch file like this

@echo off
cd /d  C:\Program Files\WindowsApps
DISM.exe /Online /Remove-ProvisionedAppxPackage /PackageName:B9ECED6F.ASUSCalculator_1.0.0.18_neutral__qmba6cd70vzyy
DISM.exe /Online /Remove-ProvisionedAppxPackage /PackageName:B9ECED6F.AsusConverter_1.0.0.27_neutral__qmba6cd70vzyy
DISM.exe /Online /Remove-ProvisionedAppxPackage /PackageName:B9ECED6F.TheWorldClock_1.0.0.6_neutral__qmba6cd70vzyy
DISM.exe /Online /Remove-ProvisionedAppxPackage /PackageName:Microsoft.Adera_1.0.0.4957_x86__8wekyb3d8bbwe
DISM.exe /Online /Remove-ProvisionedAppxPackage /PackageName:Microsoft.BingFinance_1.2.0.135_x64__8wekyb3d8bbwe
....
pause

Run the batch file as Administrator. This removed all packages in WindowsApps directory: 34 folders, 1.5GB.

(in 2016) one can uninstall Windows Store apps using free GeekUninstaller app

It's a super small & fast guy, also cleans up stuff in registry. Works on Win10 too