I've worked mostly with Gearman (made by Danga who also created memcached, mogilefs and other awesomesauce).
It's stable, fast and has API libraries for most languages which can create clients and workers. You may have to do some configuration/customisation to get it to do exactly what you're after but it's a great place to start.
If you've been "backgrounding" jobs (for async tasks for example where the client wants to fire and forget) Gearman has the option to have a persistent queue. There're a few options for persistence...
1) You can use a local SQLite file. Fast and fine for jobs you don't mind losing once if your entire box goes down. (Cache busting comes to mind)
2) You can use MySQL. If a job server dies, you can restart it and point it at the same MySQL instance. If a job server dies and the entire MACHINE is down, you can spin up another gearmand instance on another machine and point it at the right place.
If you are submitting "foregrounded" tasks, meaning your client requires a response, Gearman's way of handling failure is pretty simple. When gearmand (the server) dies, the client will see you lost a socket connection. It is then up to the client to determine what to do in that failure scenario. It sounds like in your case, you just want to resubmit it. This should be pretty easy to do.
As an FYI, I'm currently the maintainer of the python-gearman 2.x series API. We (derwiki and I) have been using Gearman in production for the past few months now and it's worked out pretty well for us. Implementation's a snap and running the daemon's pretty trivial.
A decent set up is multiple job servers and having worker daemons for the difference queues on multiple machines. As long as you have at least one job server and worker daemon going, you're in business (and you should probably put a Nagios alert on that stuff anyway). It's naive balancing, but it will taking you surprisingly far (we've been using this in production for about 6 months). That said, it's got it's own set of quirks: job servers accepting jobs when they're unable to process them while they replay a transaction log for starters -- and there's a few other subtle "job complete" bugs we haven't been able to figure out yet.
It's stable, fast and has API libraries for most languages which can create clients and workers. You may have to do some configuration/customisation to get it to do exactly what you're after but it's a great place to start.
http://gearman.org/