The problem was that I had exceeded the cache limit. Increasing it with APT::Cache-Limit "300000"; in /etc/apt/apt.conf.d/99local cured the problem. Thanks to Richard Tabor for spotting this.