Did you look at beanstalk? It has both of the features you're looking for: the ability to set a delay and when a job experiences an error it will be placed in the "buried" queue (which is like your Dead Letter Queue)

http://kr.github.com/beanstalkd/

It has client libraries in most languages and also definitely won't require the use of polling.