Struggling again to get a decent amount of entropy on a headless squeeze server.
So I just found that in squeeze-backports and wheezy there's a package for haveged.
This had an instant effect - instead of hovering around 150 in /proc/sys/kernel/random/entropy_avail - it's now moving between 1k (default minimum is set to 1024 in /etc/default/haveged) and ca 4k (IIRC the pool itself is only 4k big).