All tangled up in IF and ELIF and TRY
def remove():
    ''' see if any existing registrations match our python version and register ours if not '''

    if CurrentUser:


The python style guide reserves CamelCase for class names. If this is a global constant it should be CURRENT_USER. If its not a global constant, it shouldn't be accessed as a global variable.

        match = True if our_version in CurrentUser else False


Just use match = our_version in CurrentUser 

        versions = CurrentUser
    elif AllUsers:
        match = True if our_version in AllUsers else False
        versions = AllUsers



    else:
        print '\nOur version (%s) not registered to "%s", skipping...' % (our_version, versions[our_version])

    try:
        if match:
            print '\nVersion matches ours, calling deRegisterPy...'
            deRegisterPy(pycore_regpath,our_version)
    except:
        raise


What??? the try..except does nothing if you just raise the error right away

def deRegisterPy(pycore_regpath, version):


Python style guide recommends lower_case_with_underscores for functions names

    ''' remove this python install from registry '''
    pycore_regpath = pycore_regpath + version   # e.g. 'SOFTWARE\Python\Pythoncore\2.7'
    try:
        reg = OpenKey(HKEY_LOCAL_MACHINE, pycore_regpath)
        installpath = QueryValue(reg, installkey) # win32


Why are you taking the time to point out that its win32 here?

        if installpath == our_installpath:
            print '\nexisting python matches ours, removing...\n'
            # print '(%s vs %s)' % (installpath, our_installpath)


Don't leave dead code in comments

            for subkey in ['\\InstallPath', '\\PythonPath']:
                DeleteKey(HKEY_LOCAL_MACHINE, pycore_regpath + subkey)
            DeleteKey(HKEY_LOCAL_MACHINE, pycore_regpath)
            print "--- Python %s, %s is now removed!" % (our_version, our_installpath)
        CloseKey(reg)
    except EnvironmentError:
        print 'EnvironmentError', EnvironmentError()


What are you trying to do here? You construct a new EnviromentError object, and then print it. But that's a pointless thing to do

        raise


If you are just going to raise the error again, not a whole lot of point in printing it anyways
            return

Do you realize that nothing after the raise will be executed, so this return will have no effect?

    except WindowsError:
        print "Strange, we've hit an exception, perhaps the following will say why:"
        print WindowsError()


You seem to be confused about how to catch errors, you want:

except WindowsError as error:
    print error


But really you don't need to do that: just let the exceptions fly and python will print them when it exits due to the error

        raise
        return


Again, the return will never be reached

    CloseKey(reg)


If an exception occurs, this will never be called. You should put it in a finally block or something

# main
if args['action']=='install':
    install()
elif args['action']=='remove':
    remove()


You should really put logic like this in a main function.

Any my rewrite of your whole linked file. No testing has been done. But it should give you something of an idea of what you can do.

#!/usr/bin/env python

import sys
from _winreg import *

import argparse, sys
import os.path

PYTHON_VERSION = "%d.%d" % sys.version_info[0:2]

# the registry key paths we'll be looking at &amp; using
PYCORE_REGISTRY_PATH = ("SOFTWARE","Python","Pythoncore")
INSTALL_KEY = "InstallPath"
PYTHON_KEY = "PythonPath"
PYTHONPATH = ";".join( os.path.join(sys.prefix, sub) for sub in ["", "Lib", "DLLs"])

class RegisteryKeyNotFound(Exception):
    pass

class RegisteryKey(object):
    def __init__(self, hive):
        self._key = key

    def _path_from(self, segments):
        if not isinstance(segments, tuple):
            segments = (segments,)

        return "\\".join(segments)

    def __getitem__(self, segments):
        try:
            subkey = _winreg.OpenKey(self._key, self._path_from(segments))
        except WindowsError:
            # should really check the error
            # to make sure that key not found is the real problem
            raise RegisteryKeyNotFound(path)
        return RegisteryKey(subkey)

    def get_or_create(self, segments):
        subkey = _winreg.CreateKey(self._key, self._path_from(segments))
        return RegisteryKey(subkey)


    def value(self, segments):
        return _winreg.QueryValue(self._key, self._path_from(segments))

    def delete(self, segments):
        _winreg.DeleteKey(self._key, self._path_from(segments))

    def set_value(self, segments, value):
        _winreg.SetValue(self._key, self._path_from(segments), REG_SZ, value)

    def __iter__(self):
        index = 0
        while True:
            try:
                yield RegisteryKey(EnumKey(key, index))
            except WindowsError:
                # add check to make sure correct here was gotten
                break
            else:
                index += 1

    def __del__(self):
        _winreg.CloseKey(self._key)

HIVE_LOCAL_MACHINE = RegisteryKey(HKEY_LOCAL_MACHINE)
HIVE_CURRENT_USER = RegisteryKey(HKEY_CURRENT_USER)

def get_existing(hive):
    ''' retrieve existing python registrations '''

    try:
        key = hive[PYCORE_REGISTRY_PATH]
    except RegisteryKeyNotFound:
        return {}

    versions = {}
    for version in key:
        versions[version] = version.value(INSTALL_KEY)                           # e.g. {'2.7' = 'C:\\Python27'}

    return versions

def register_python(version):
    ''' put this python install into registry '''
    try:
        reg = HIVE_LOCAL_MACHINE[PYCORE_REGISTRY_PATH][version]
    except RegisteryKeyNotFound:
        reg = HIVE_LOCAL_MACHINE.get_or_create(PYCORE_REGISTRY_PATH).get_or_create(version)
        reg.set_value(INSTALL_KEY, sys.prefix)
        reg.set_value(PYTHON_KEY, PYTHONPATH)
        print "--- Python %s is now registered to %s!" % (PYTHON_VERSION, sys.prefix)
    else:
        print reg.value(INSTALL_KEY)

    if reg.value(INSTALL_KEY) == sys.prefix and reg.value(PYTHON_KEY) == PYTHONPATH:
        print "=== Python %s is already registered!" % (PYTHON_VERSION)
    else:
        print "*** Unable to register!"
        print "*** You probably have another Python installation!"

def deregister_python(version):
    ''' remove this python install from registry '''
    reg = HIVE_LOCAL_MACHINE[PYCORE_REGISTRY_PATH][version]
    install_path = reg.value(INSTALL_KEY)
    if install_path == sys.prefix:
        print '\nexisting python matches ours, removing...\n'
        for subkey in ['InstallPath', 'PythonPath']:
            reg.delete(subkey)
        reg.delete()
        print "--- Python %s, %s is now removed!" % (PYTHON_VERSION, sys.prefix)

def install(installed_versions):
    ''' see if any existing registrations match our python version, and if not, register ours '''

    print '\n...installing'

    if PYTHON_VERSION in installed_versions:
        print '\nOur version (%s) already registered to "%s", skipping...' % (PYTHON_VERSION, installed_versions[PYTHON_VERSION])
    else:
        print '\nPutting python from environment into registry...\n'
        register_python()

def remove(installed_versions):
    ''' see if any existing registrations match our python version and register ours if not '''
    #print args
    if PYTHON_VERSION in installed_versions:
        deregister_python()
    else:
        print '\nOur version (%s) not registered, skipping...' % (PYTHON_VERSION)



# @url http://stackoverflow.com/questions/4042452/display-help-message-with-python-argparse-when-script-is-called-without-any-argum
# display the usage message when it is called with no arguments
class MyParser(argparse.ArgumentParser):
    def error(self, message):
        sys.stderr.write('error: %s\n' % message)
        self.print_help()
        sys.exit(2)



def main():
    parser=MyParser()
    parser.add_argument('action', help='one of "install" or "remove" ')
    args = parser.parse_args()

    current_user_versions = get_existing(HIVE_CURRENT_USER)
    local_machine_versions = get_existing(HIVE_LOCAL_MACHINE)

    print '\nFound in Current User:'
    for key, value in current_user_versions.items():
        print "\t%s - %s" % (key, value)
    print '\nFound in All Users:'
    for key, value in local_machine_version.items():
        print "\t%s - %s" % (key, value)

    all_versions = {}
    all_versions.update(current_user_versions)
    all_versions.update(local_machine_versions)


    if args.action == 'install':
        install(all_versions)
    elif args.action == 'remove':
        remove(all_versions)
    else:
        print '\nInvalid action specified. I only understand "install" and "remove". '

if __name__ == '__main__':
    main()


Some notes:


The _winreg interface is rather low level. You can make code a lot clearer by wrapping it in something more pythonic. I've only taken a first stab at an interface, and it probably could be done a lot better. 
You split out CurrentUser and LocalMachine but treated them pretty much exactly the same. The code can be simplified by merging them into a giant dictionary of versions
you remove python from LocalMachine but not CURRENT_USER. That seems odd but I've not changed it.