As an additional thing I do rolling deploys where I just create an entirely new VM and add it before removing the old one. This just means that I don't have to recycle a node that might potentially have some state on it.
See http://engineeringblog.yelp.com/2015/04/true-zero-downtime-h... or http://inside.unbounce.com/product-dev/haproxy-reloads/ for solutions that are even better than this one.
The challenge is that whether HAProxy's own support for graceful restarts works depends on which OS and kernel version you're running and what network socket features are supported, so ensuring that's all kosher is a bit of a challenge. I took the approach that it's simpler to do something that takes a bit longer without having to worry about all that.