And before I just propose a different change, I'd like to try and prove
that it fixes the above issue.  For a package with an update, let

p := is a built-in package
q := built-in packages should be upgradede

The previous implementation with xor (p ⊻ q) correctly decides to
upgrade or not-upgrade the package in three of the four possible cases

p q   upgrade? 
--------------
t f   f
t t   t
f t   f        <-- this was Andreas case
f f   t

But since non-built-in packages should always be upgraded, we need to
change the condition to only be false when we have a built-in package
but `package-install-upgrade-built-in' is non-nil:

      ¬ (¬ q ∧ p)
    = ¬¬ q ∨ ¬p
    = q ∨ ¬p

as we see, this should solve the issue:

p q   upgrade? (p ∨ ¬q)
--------------
t f   f
t t   t
f t   t
f f   t

Does this look OK?