I dug myself a gre tunnel between two grsec-linux kernels. The gre packets are reaching both machines, but they can't ping or do anything else via the tunnel. Same setup works fine on two non grsec kernels, so I'm guessing there is some specific sysctl option or something similar I have to change to make it work.
For the doubting crowd: I've had everything I did checked by both the #archlinux and the #netfilter guys. It should work, but somehow it doesn't. And as I said I did exactly the same steps on two non grsec machines and there it worked right away.
If anyone has any idea I'd be delighted, obviously. I've been sitting over this for about seven hours now. The fun of tinkering around left me at about a quarter of that time frame. Please help.