For simplicity I'll call the package to be configured with A. My last patch failed to take into account the scenario where other packages depended on A where there were no version mismatches. Only the case where there would have been a version mismatch after the configure was checked for.
The check for dependencies after the install would see that A's state is unpacked, what would cause deppossi_ok_found to return as status deferred. But since we don't test for A's dependencies here but the packages that depend on A instead we don't care of that information. Hence we can just leave the status as ok even if the check returns deferred. I must confess that I still don't understand the full implications of this patch. But hopefully this is nearer to a correct fix already.
--- dpkg-1.13.11/src/packages.c 2005-06-06 07:07:12.000000000 +0300 +++ ../fix/dpkg-1.13.11/src/packages.c 2005-10-24 20:14:57.000000000 +0300 @@ -408,6 +408,43 @@ int dependencies_ok(struct pkginfo *pkg, internerr("unknown value for found"); } } + + if (!removing && pkg->installed.depended) { + for (possi= pkg->installed.depended; possi; possi = possi->next) { + if (possi->up->type != dep_depends && possi->up->type != dep_predepends) + continue; + matched= 0; varbufreset(&oemsgs); + thisf= deppossi_ok_found(possi->ed, possi->up->up, 0, 0, &matched, possi, + &interestingwarnings, &oemsgs); + + switch (thisf) { + case 0: + ok= 0; + case 2: + varbufaddstr(aemsgs, " "); + varbufaddstr(aemsgs, possi->up->up->name); + varbufaddstr(aemsgs, _(" depends on ")); + varbufdependency(aemsgs, possi->up); + if (interestingwarnings) { + /* Don't print the line about the package to be removed if + * that's the only line. + */ + varbufaddstr(aemsgs, _("; however:\n")); + varbufaddc(&oemsgs, 0); + varbufaddstr(aemsgs, oemsgs.buf); + } else { + varbufaddstr(aemsgs, ".\n"); + } + break; + case 1: /* deferred installs do not apply here. */ + case 3: + break; + default: + internerr("unknown value for found"); + } + } + } + if (ok == 0 && (pkg->clientdata && pkg->clientdata->istobe == itb_remove)) ok= 1;