Memory fragmentation seems to play a role too. Even if you have (barely) enough free RAM, machines can start swapping and a Redis server in that state is bound to wake you up at night... :(
If you run a server with anything but "swapoff -a" you're doing it wrong. (or even having any swap partition in /etc/fstab).
If the server has to swap, get more RAM or scale your stuff out but never swap.