Since no one confirmed this problem, I looked further for local reasons and found that I'm running a self-compiled, i.e. non-debian kernel.
Activating the current debian kernel solved this issue. Thank you Alessandro for maintaining the valgrind package. Lars
