dpkg wrongly claims that a foreign-arch package is disappeared by a removed native-arch package

This bug has been hovering in the background for a while with multiarch, and I've recently pinned it down.

When a native-architecture package is removed and a foreign-architecture package gets installed, dpkg makes a wrong calculation somewhere which, on upgrade, results in the foreign-architecture package being "disappeared" from the database. This results in all the files from the package being left on disk (orphaned), and apt happily removing any dependencies of the package that were auto-installed.

Reproducer:

1.Download the 64-bit skype package from <http://www.skype.com/intl/en-us/get-skype/on-your-computer/linux/downloading.ubuntu64> and install it with dpkg (fixing up the dependencies with 'apt-get -f install').

2. Install the skype:i386 package from the Canonical Partner repository for oneiric, using either Software Center or 'apt-get install skype:i386'.
$ sudo apt-get install skype:i386
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages will be REMOVED:
  skype
The following NEW packages will be installed:
  skype:i386
0 upgraded, 1 newly installed, 1 to remove and 156 not upgraded.
Need to get 0 B/23.6 MB of archives.
After this operation, 489 kB of additional disk space will be used.
Do you want to continue [Y/n]?

3. Confirm that skype is now removed, but not purged.
$ dpkg -l skype:*
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name Version Description
+++-==============-==============-============================================
rc skype 2.2.0.35-1 Skype
ii skype:i386 2.2.0.35-0onei VOIP and instant messaging client

4. Make sure at least one package is out of date on the system and run 'sudo apt-get upgrade':
[...]
Preparing to replace libasound2-python 1.0.24.1-0ubuntu8 (using .../libasound2-p
ython_1.0.24.1-0ubuntu10_amd64.deb) ...
Unpacking replacement libasound2-python ...
(Noting disappearance of skype:i386, which has been completely replaced.)
[...]
Setting up unity-2d (4.12.0-0ubuntu1) ...
Processing triggers for libc-bin ...
ldconfig deferred processing now taking place
Processing triggers for python-support ...
The following package disappeared from your system as
all files have been overwritten by other packages:
  skype
Note: This is done automatic and on purpose by dpkg.
$

5. See that skype:i386 really has been disappeared, and skype:amd64 is still in state 'rc'.
$ dpkg -l skype:*
Desired=Unknown/Install/Remove/Purge/Hold
| Status=Not/Inst/Conf-files/Unpacked/halF-conf/Half-inst/trig-aWait/Trig-pend
|/ Err?=(none)/Reinst-required (Status,Err: uppercase=bad)
||/ Name Version Description
+++-==============-==============-============================================
rc skype 2.2.0.35-1 Skype
un skype:i386 <none> (no description available)

ProblemType: Bug
DistroRelease: Ubuntu 11.10
Package: dpkg 1.16.0.3ubuntu4
ProcVersionSignature: Ubuntu 3.0.0-11.18-generic 3.0.4
Uname: Linux 3.0.0-11-generic x86_64
ApportVersion: 1.23-0ubuntu2
Architecture: amd64
Date: Fri Sep 30 13:48:16 2011
InstallationMedia: Ubuntu 10.04.1 LTS "Lucid Lynx" - Release amd64 (20100816.1)
ProcEnviron:
 PATH=(custom, user)
 LANG=en_US.UTF-8
 SHELL=/bin/bash
SourcePackage: dpkg
UpgradeStatus: Upgraded to oneiric on 2011-09-23 (6 days ago)
modified.conffile..etc.dpkg.dpkg.cfg: [modified]
mtime.conffile..etc.dpkg.dpkg.cfg: 2011-08-16T12:02:14.243634