I've found the problem myself.
I am using an SSD. That's why I mounted /var/cache to RAM(via tmpfs) in order to limit write access on the SSD. Debconf puts it's cache to /var/cache/debconf when installing it. But this is on RAM. So after every restart apt-get only worked if I reinstalled deconf.
Of course the definite solution in this case was to run
mkdir /var/cache/debconf
in a bootup script.