linux routing bug?
It is indeed a linux kernel bug, probably since version 2.6.39. I have posted the question to lkml and netdev lists (see the thread at https://lkml.org/lkml/2011/11/18/191), and it was just discussed in a different netdev thread at http://www.spinics.net/lists/netdev/msg179687.html
The current solution now is either a reboot or to flush all routes and wait 10 minutes for the icmp redirects to expire. To prevent it to happen again,
echo 0 >/proc/sys/net/ipv4/conf/eth0/accept_redirects
helps.