--- a/browser/installer/windows/nsis/maintenanceservice_installer.nsi
+++ b/browser/installer/windows/nsis/maintenanceservice_installer.nsi
@@ -182,16 +182,30 @@ Section "MaintenanceService"
     ExecWait '"$INSTDIR\$TempMaintServiceName" install'
   ${Else}
     ; The upgrade cmdline is the same as install except
     ; It will fail if the service isn't already installed.
     ExecWait '"$INSTDIR\$TempMaintServiceName" upgrade'
   ${EndIf}
 
   WriteUninstaller "$INSTDIR\Uninstall.exe"
+
+  ; Since the Maintenance service can be installed either x86 or x64,
+  ; always use the 64-bit registry.
+  ${If} ${RunningX64}
+    ; Previous versions always created the uninstall key in the 32-bit registry.
+    ; Clean those old entries out if they still exist.
+    SetRegView 32
+    DeleteRegKey HKLM "${MaintUninstallKey}"
+    ; Preserve the lastused value before we switch to 64.
+    SetRegView lastused
+
+    SetRegView 64
+  ${EndIf}
+
   WriteRegStr HKLM "${MaintUninstallKey}" "DisplayName" "${MaintFullName}"
   WriteRegStr HKLM "${MaintUninstallKey}" "UninstallString" \
                    '"$INSTDIR\uninstall.exe"'
   WriteRegStr HKLM "${MaintUninstallKey}" "DisplayIcon" \
                    "$INSTDIR\Uninstall.exe,0"
   WriteRegStr HKLM "${MaintUninstallKey}" "DisplayVersion" "${AppVersion}"
   WriteRegStr HKLM "${MaintUninstallKey}" "Publisher" "Mozilla"
   WriteRegStr HKLM "${MaintUninstallKey}" "Comments" "${BrandFullName}"
@@ -199,21 +213,16 @@ Section "MaintenanceService"
   ${GetSize} "$INSTDIR" "/S=0K" $R2 $R3 $R4
   WriteRegDWORD HKLM "${MaintUninstallKey}" "EstimatedSize" $R2
 
   ; Write out that a maintenance service was attempted.
   ; We do this because on upgrades we will check this value and we only
   ; want to install once on the first upgrade to maintenance service.
   ; Also write out that we are currently installed, preferences will check
   ; this value to determine if we should show the service update pref.
-  ; Since the Maintenance service can be installed either x86 or x64,
-  ; always use the 64-bit registry for checking if an attempt was made.
-  ${If} ${RunningX64}
-    SetRegView 64
-  ${EndIf}
   WriteRegDWORD HKLM "Software\Mozilla\MaintenanceService" "Attempted" 1
   WriteRegDWORD HKLM "Software\Mozilla\MaintenanceService" "Installed" 1
   DeleteRegValue HKLM "Software\Mozilla\MaintenanceService" "FFPrefetchDisabled"
 
   ; Included here for debug purposes only.  
   ; These keys are used to bypass the installation dir is a valid installation
   ; check from the service so that tests can be run.
   ; WriteRegStr HKLM "${FallbackKey}\0" "name" "Mozilla Corporation"
@@ -313,20 +322,19 @@ Section "Uninstall"
   Push "$APPDATA\Mozilla\logs\maintenanceservice-uninstall.log"
   Call un.RenameDelete
   RMDir /REBOOTOK "$APPDATA\Mozilla\logs"
   RMDir /REBOOTOK "$APPDATA\Mozilla"
   RMDir /REBOOTOK "$INSTDIR\logs"
   RMDir /REBOOTOK "$INSTDIR\update"
   RMDir /REBOOTOK "$INSTDIR"
 
-  DeleteRegKey HKLM "${MaintUninstallKey}"
-
   ${If} ${RunningX64}
     SetRegView 64
   ${EndIf}
+  DeleteRegKey HKLM "${MaintUninstallKey}"
   DeleteRegValue HKLM "Software\Mozilla\MaintenanceService" "Installed"
   DeleteRegValue HKLM "Software\Mozilla\MaintenanceService" "FFPrefetchDisabled"
   DeleteRegKey HKLM "${FallbackKey}\"
   ${If} ${RunningX64}
     SetRegView lastused
   ${EndIf}
 SectionEnd

--- a/browser/installer/windows/nsis/uninstaller.nsi
+++ b/browser/installer/windows/nsis/uninstaller.nsi
@@ -195,26 +195,35 @@ Function un.UninstallServiceIfNotUsed
     IntOp $0 $0 + 1
   ${Loop}
 
   ; Restore back the registry view
   ${If} ${RunningX64}
     SetRegView lastUsed
   ${EndIf}
   ${If} $0 == 0
-    ; Get the path of the maintenance service uninstaller
+    ; Get the path of the maintenance service uninstaller.
+    ; Look in both the 32-bit and 64-bit registry views.
+    SetRegView 32
     ReadRegStr $1 HKLM ${MaintUninstallKey} "UninstallString"
+    SetRegView lastused
+
+    ${If} $1 == ""
+    ${AndIf} ${RunningX64}
+      SetRegView 64
+      ReadRegStr $1 HKLM ${MaintUninstallKey} "UninstallString"
+      SetRegView lastused
+    ${EndIf}
 
     ; If the uninstall string does not exist, skip executing it
-    StrCmp $1 "" doneUninstall
-
-    ; $1 is already a quoted string pointing to the install path
-    ; so we're already protected against paths with spaces
-    nsExec::Exec "$1 /S"
-doneUninstall:
+    ${If} $1 != ""
+      ; $1 is already a quoted string pointing to the install path
+      ; so we're already protected against paths with spaces
+      nsExec::Exec "$1 /S"
+    ${EndIf}
   ${EndIf}
 
   ; Restore the old value of $1 and $0
   Pop $1
   Pop $0
 FunctionEnd
 
 ################################################################################