To answer this question I'm going to highlight a couple of points for you to consider.

1. Until official support has been announced, don't use the non-official PowerShell PackageManagement provider for Chocolatey. It is an unsupported preview subject to bugs and security flaws (it was also not created by the Chocolatey team). Instead use choco.exe, or another official provider.
2. AutoUninstaller is the resource in official Chocolatey clients that can remove natively installed software from packages that do not contain an uninstall script. It's important to note that you also need to install from those official clients. More information at https://chocolatey.org/docs/commands-uninstall

Why are these packages still present after uninstall-package?

It really depends on what you used to install the packages and whether Chocolatey was able to capture a snapshot for auto uninstaller.

Many packages do not require an uninstall script. Some do. When they are an MSI and are upgraded outside of Chocolatey (like Chrome does automatically), you either need Package Synchronizer or an uninstall script to uninstall the software.

Is there a best-practice way to do this?

If this is for organizational use, and you have a low tolerance for breakages, we recommend you build your own internal packages. Then you can completely control the process and have a repeatable, reliable process. This is how hundreds of organizations that use Chocolatey currently have enhanced their installation processes. They typically already have software installers already present on some internal file share and build packages around them to take advantage of better automation processes (versus old batch files they may have been using, or worse, manually installing from).

If you are curious on why you should build your own, see https://chocolatey.org/docs/community-packages-disclaimer (it attempts to highlight the issues with a public repository and it being subjected to distribution rights, something an internal repository is not subject to).

Is there a best-practice way to script python's re-installation so this won't happen again?

Use a configuration management tool like Puppet, Chef, Ansible, or DSC with the Chocolatey provider. https://chocolatey.org/docs/features-infrastructure-automation

This is how you create automation across all of your machines and take advantage of package management.

You can check to see if there are such specific steps on the Python site. I removed the Python packages with Uninstall-Package and it worked as expected. Try repairing the installation using the Python installer, then run the Uninstall-Package cmdlet again.

Also it seems the packages should be removed in some specific order. I removed the documents and libraries first, and the core interpreter and executables last.

So after some time of me and my colleague troubleshooting this, we gained a better understanding of the situation and what actually happened. This doesn't solve what we were trying to do originally (deploy Python 3.8.1 MSI's through WSUS), but it at least helps us clean up. Hopefully this helps another admin out there who may have experienced something similar to this with WSUS Package Publisher or something else!!

We're deploying Python through WSUS, so that means that all local machines install Python as NTAUTH\SYSTEM. This explains why Python was installing correctly, without complaints, in the location I specified in the .MST (C:\Program Files\Python38).

For some reason, the Python MSI's all ignore the ALLUSERS=1 call in the .MST, and by specifying it as a parameter. No idea why (maybe someone from the Python team or someone with a deeper understanding could chime in? :) ).

The result of this means, from my understanding/testing, that the installer detects that it's not running as an elevated process, and therefore installs the MSI as user NTAUTH\SYSTEM, for NTAUTH\SYSTEM, placing the keys for Python launcher etc in HKCU instead of HKLM. But because of the .MST and the access rights that NTAUTH\SYSTEM has, it places the installation files in C:\Program Files\Python38 as requested.

This explains why installations would fail, uninstallation was impossible no matter what, and why our Python Launcher was behaving weirdly despite PATH being set correctly.

• Installations would fail because the keys would all still be placed in the HKLM\Software\Microsoft\Windows\CurrentVersion\Uninstall\
• The installers never appeared in Installed Applications despite successful installation, because it was installed for the NTAUTH\SYSTEM and not All Users
• The uninstallation through MSIEXEC or by right clicking the MSI would claim that it wasn't installed, because Python was technically not installed for either the system (aka All Users when elevated), nor the user trying to uninstall it (aka my user account, without elevation).
• py -0 wasn't picking up the Py38 installation despite picking up other versions, because the launcher was searching in the HKLM keys, which 381 wasn't installing in.

So to clean this huge mess up, we needed to uninstall all of the Python 3.8.1 MSI's as NTAUTH\SYSTEM, and without elevation. There are several ways to do this - either by downloading and using PSEXEC to launch a CMD or Powershell as System (psexec64.exe -sid powershell.exe) and running MSIEXEC through that, or (the approach we took) create a Scheduled Task on the machine, have it run as NTAUTH\SYSTEM, without the highest privilages, and uninstall anything which had "Python 3.8.1*" property. A quick Powershell script for this:

$products = Get-WmiObject Win32_Product

foreach ($pkg in (
        "Python 3.8.1 Tcl*",
        "Python 3.8.1 Util*",
        "Python 3.8.1 Test*",
        "Python 3.8.1 Dev*",
        "Python 3.8.1 Documentation*",
        "Python 3.8.1 pip*",
        "Python 3.8.1 Standard*",
        "Python 3.8.1 Exe*",
        "Python 3.8.1 Core*",
        "Python 3.8.1 Add*",
        "Python Launcher*"
    )) {
    $products | Where-Object {
        ($_.Name -like $pkg)
    } | Select-Object -ExpandProperty LocalPackage | Foreach-Object {
        Start-Process -FilePath "msiexec.exe" -ArgumentList "/x $_ /QN" -Wait
    }
}

get-wmiobject Win32_Product | where-object {$_.Name -like "Python*"} | Format-Table Name, LocalPackage

Here's the steps (my non-computer-savvy girlfriend had to figure this one out for me, but unlike all the far more complicated processes one can find online, this one works)

1. Open Control Panel
2. Click "Uninstall a Program"
3. Scroll down to Python and click uninstall for each version you don't want anymore.

This works on Windows 7 out of the box, no additional programs or scripts required.