Comment 15 for bug 503765

See also

https://lists.debian.org/debian-dpkg/2012/03/msg00063.html

where it says

As above, most of pkgstates is actually private to aptitude. Some of
it is duplicated for convenience, however, aptitude does take measures
to keep in sync. with dpkg/apt when it is started. *Admitedly, this
process fails quite often.* (emphasis is mine)

and

For example, removing a package with apt-get can lead to aptitude
trying to reinstall that package. *Note that aptitude is aware that
the package has been removed, it just mistakenly believes the user has
requested it be installed again.*

So, it looks like aptitude is remembering pending actions, even when they are not anymore relevant or applicable.

IMHO, this 'session' idea of aptitude is quite wrong in itself. You just cannot remember pending actions without having a lock on the package database, preventing others from changing the system state. I suggest modifying the packaging of aptitude to set up a cron script erasing pkgstates every night.