How do I implement my Installer correctly

I'm trying to create an installer, which automagically updates the installed component. Therefore I have created an installer-project, with following settings:

ProductCode: {9835AE3C-1CED-4FC6-85E1-D2DC8093E9F4}
ProductName: Foo
UpgradeCode: {02FD8E1A-A552-47AE-BDAA-F165702DE8DC}
Version: 1.2.002

When I change my Version-attribute, a new ProductCode gets generated (how I understood, the grouping on the product is done via UpgradeCode and the specific version is bound to ProductCode).

My Custom-Actions look like this:

Sooo ... here we have my installer-class:

[RunInstaller(true)]
// my .cs-file
public partial class Installer : System.Configuration.Install.Installer
{
    public Installer()
    {
        this.InitializeComponent();
    }

    protected override void OnAfterInstall(System.Collections.IDictionary savedState)
    {
        base.OnAfterInstall(savedState);

        using (var serviceController = new ServiceController(Settings.Service.Name))
        {
            serviceController.Start();
            serviceController.WaitForStatus(ServiceControllerStatus.Running);
        }
    }

    protected override void OnBeforeUninstall(System.Collections.IDictionary savedState)
    {
        base.OnBeforeUninstall(savedState);

        using (var serviceController = new ServiceController(Settings.Service.Name))
        {
            serviceController.Stop();
            serviceController.WaitForStatus(ServiceControllerStatus.Stopped);
        }
    }
}


// my designer
partial class Installer
{
    private ServiceInstaller ServiceInstaller;
    private ServiceProcessInstaller ServiceProcessInstaller;

    /// <summary>
    /// Required designer variable.
    /// </summary>
    private System.ComponentModel.IContainer components = null;

    /// <summary> 
    /// Clean up any resources being used.
    /// </summary>
    /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
    protected override void Dispose(bool disposing)
    {
        if (disposing && (components != null))
        {
            components.Dispose();
        }
        base.Dispose(disposing);
    }

    #region Component Designer generated code

    /// <summary>
    /// Required method for Designer support - do not modify
    /// the contents of this method with the code editor.
    /// </summary>
    private void InitializeComponent()
    {
        this.ServiceProcessInstaller = new System.ServiceProcess.ServiceProcessInstaller();
        this.ServiceInstaller = new System.ServiceProcess.ServiceInstaller();
        // 
        // ServiceProcessInstaller
        // 
        this.ServiceProcessInstaller.Account = System.ServiceProcess.ServiceAccount.LocalService;
        this.ServiceProcessInstaller.Password = null;
        this.ServiceProcessInstaller.Username = null;
        // 
        // ServiceInstaller
        // 
        this.ServiceInstaller.ServiceName = "Foo";
        this.ServiceInstaller.StartType = System.ServiceProcess.ServiceStartMode.Automatic;

    }

    #endregion
}

The initial installation is not the problem - everything works fine (installation, automatic start, ...). But when I try to install a new .msi-package with the same UpgradeCode but different ProductCode, the installer fails with "Error 1001: The specified service already exists" - which makes me believe, that any uninstall-handler (or invocation) is not being called and that the UpgradeCode/Productcode-magic does not work ...
So, my question: Where is the path (overriding) which handles (or should handle) the uninstallation? What would be the correct implementation?

edit:
Setting of HKEY_LOCAL_MACHINE\Software\Policies\Microsoft\Windows\Installer:Logging is iwemv - output @ pastebin (actually I have different codes in my scenario as in my question here).
as we see in line 161ff, the previous version is found:

MSI (c) (50:04) [10:03:31:319]: Doing action: AppSearch
Aktion gestartet um 10:03:31: AppSearch.
MSI (c) (50:04) [10:03:31:319]: Note: 1: 2262 2: AppSearch 3: -2147287038 
Aktion beendet um 10:03:31: AppSearch. Rückgabewert 1.
MSI (c) (50:04) [10:03:31:319]: Doing action: FindRelatedProducts
Aktion gestartet um 10:03:31: FindRelatedProducts.
MSI (c) (50:04) [10:03:31:319]: PROPERTY CHANGE: Adding PREVIOUSVERSIONSINSTALLED property. Its value is '{C4C4318A-2F89-416B-A48C-76BD035EB52B}'.
Aktion beendet um 10:03:31: FindRelatedProducts. Rückgabewert 1.

line 272 invocation @ client

MSI (c) (50:04) [10:03:31:413]: Switching to server: TARGETDIR="C:\Program Files (x86)\MyCompany\Foobar\" ALLUSERS="1" PREVIOUSVERSIONSINSTALLED="{C4C4318A-2F89-416B-A48C-76BD035EB52B}" VSDNETURLMSG="Dieses Setup erfordert die Version 4.0 von .NET Framework. Installieren Sie .NET Framework, und führen Sie Setup erneut aus. .NET Framework kann über das Internet bezogen werden. Möchten Sie es jetzt beziehen?" VSDNETMSG="Dieses Setup erfordert die Version 4.0 von .NET Framework. Installieren Sie .NET Framework, und führen Sie Setup erneut aus." CURRENTDIRECTORY="D:\Foo\Release" CLIENTUILEVEL="0" CLIENTPROCESSID="5200" USERNAME="MyCompany Support" COMPANYNAME="MyCompany GmbH" SOURCEDIR="D:\Foo\Release\" ACTION="INSTALL" EXECUTEACTION="INSTALL" ROOTDRIVE="D:\" INSTALLLEVEL="1" SECONDSEQUENCE="1"  ADDLOCAL=DefaultFeature

line 313 invocation @ server

MSI (s) (A4:6C) [10:03:41:219]: Command Line: TARGETDIR=C:\Program Files (x86)\MyCompany\Foobar\ ALLUSERS=1 PREVIOUSVERSIONSINSTALLED={C4C4318A-2F89-416B-A48C-76BD035EB52B} VSDNETURLMSG=Dieses Setup erfordert die Version 4.0 von .NET Framework. Installieren Sie .NET Framework, und führen Sie Setup erneut aus. .NET Framework kann über das Internet bezogen werden. Möchten Sie es jetzt beziehen? VSDNETMSG=Dieses Setup erfordert die Version 4.0 von .NET Framework. Installieren Sie .NET Framework, und führen Sie Setup erneut aus. CURRENTDIRECTORY=D:\Foo\Release CLIENTUILEVEL=0 CLIENTPROCESSID=5200 USERNAME=MyCompany Support COMPANYNAME=MyCompany GmbH SOURCEDIR=D:\Foo\Release\ ACTION=INSTALL EXECUTEACTION=INSTALL ROOTDRIVE=D:\ INSTALLLEVEL=1 SECONDSEQUENCE=1 ADDLOCAL=DefaultFeature ACTION=INSTALL

sooo ... action is install, and not update/uninstall/...?!

Since you asked "correctly" you should know that InstallUtil custom actions are a horrible antipattern and you are reinventing the wheel by writing code to things MSI already supports natively. You should also know that Visual Studio Deployment projects are horrible in so many ways ( in this case not exposing MSI's ability to install and control services ) that they are removed in the next release of VS11.

Some background: ( Yours is an example of a and c )

Zataoca: Custom actions are (generally) an admission of failure.

Now my advice to you is to get rid of the custom action and use a WiX merge module instead. The concept is to factor the component that has your service EXE into a merge module and then have your VDPROJ consume the merge module. ( Take a class out of a console app and move it into library and then use ILDASM to merge the library back into the console app if you will ). Use Windows Installer XML to author the merge module because 1) it actually exposes the ServiceInstall and ServiceControl tables and 2) it's FOSS.

Augmenting InstallShield using Windows Installer XML - Windows Services

Your resultant MSI will be much simpler / cleaner and your 1001 error messages will magically go away because MSI is doing the work for you.