Microsoft has noticed that AppV 5 sometimes has trouble cleaning up after itself and it looks like Microsoft has made a cleanup powershell script for AppV5. It is located here:
C:\Program Files\Microsoft Application Virtualization\Client
The command needs to be executed like so:
.\Disable-AppVClient.ps1 -ModulePath "C:\Program Files\Microsoft Application Virtualization\Client\AppvClient\AppvClient.psd1" -RemoveAllPackages -PackageInstallationRoot "D:\AppVData\PackageInstallationRoot
This powershell script will also inform you if you need to remove the packages manually because of permissions issues. I would highly recommend putting it in the shutdown script of your servers/desktops.