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.
It does handle load balancing in a nice way.
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.