Looks like I had a misconfiguration in apt.conf.d: APT::Get::Install-Recommends "false"; instead of APT::Install-Recommends "false";
No error was issued, so I assumed it worked. This line seems to be the true cause of this bug in my case. Although I do not know if trying to install missing recommendations specifically during upgrades if Install-Recommends is true is desired behavior. If it is, then this bug can be closed.
