I'm currently upgrading a stable machine to unstable (except some
buggy packages), which is mostly done, but aptitude has some issues
when I want to upgrade vlc.

First, "aptitude install -s vlc" does not gives any good solution:
all of them keep vlc at its current version.

Note that apt also fails (bug 1059068), but adding libavcodec60
(suggested in its output) makes it succeeds. With aptitude,
"aptitude install -s vlc libavcodec60" also wants to keep vlc.

If I give the packages to be removed (those listed by apt)

  aptitude install -s libavcodec59- libavfilter8- libavformat59- \
    libavif15- libsvtav1enc1- vlc

there is still an issue:

The following NEW packages will be installed:
  libavcodec60{a} libavformat60{a} libcodec2-1.2{a} libixml11{a}
  libpostproc57{a} libsvtav1enc1d1{a} libswscale7{a} libupnp17{a}
The following packages will be REMOVED:
  libavcodec59 libavfilter8 libavformat59 libavif15 libcodec2-1.0{u}
  libdav1d6{u} libgav1-1{u} libixml10{u} libnfs13{u} libplacebo208{u}
  libpocketsphinx3{u} libpostproc56{u} librubberband2{u} libsdl-image1.2{u}
  libsdl1.2debian{u} libsphinxbase3{u} libsvtav1enc1{u} libupnp13{u}
  libvidstab1.1{u} libvpx7{u} libyuv0{u} libzimg2{u} pocketsphinx-en-us{u}
The following packages will be upgraded:
  libvlc-bin libvlc5 libvlccore9 vlc vlc-bin vlc-data vlc-l10n
  vlc-plugin-access-extra vlc-plugin-base vlc-plugin-notify vlc-plugin-qt
  vlc-plugin-samba vlc-plugin-skins2 vlc-plugin-video-output
  vlc-plugin-video-splitter vlc-plugin-visualization
16 packages upgraded, 8 newly installed, 23 to remove and 78 not upgraded.
[...]
      Leave the following dependencies unresolved:
28)     libpocketsphinx3 recommends pocketsphinx-en-us

while there is no need to remove pocketsphinx-en-us.

I've attached an archive with

  /var/lib/dpkg/status
  /var/lib/aptitude/pkgstates
  /var/lib/apt/extended_states

and the resolver log of the above 3 commands.

I've noticed that this isn't included by default. I'm using

Aptitude::ProblemResolver::SolutionCost "safety, removals";