Today I learned, that Debian still does not default to the new solver1 - for reasons unknown I have assumed it's already used out of the box.
As I want to avoid having to think about it or adjust aliases again, I decided to configure it in APT's configuration2
/etc/apt/apt.conf.d/90solver
:
binary::apt::APT::Solver "3.0";