If you go with SQS, keep in mind it doesn't guarantee that messages will be received exactly once[1]. I've used SQS for large projects and this was killer because we had to implement message locking ourselves to prevent messages from being processed twice. Since then, this has been a deal breaker for using SQS again (now use Celery).
I was under the impression [1] that a message would only be received more than once if the first attempt at processing failed to complete in the lock time - for example if the queue consumer crashed. Is it more complicated than that?
Speaking of celery - I was looking at celery over the weekend. Do you know if its possible to submit jobs from languages other than Python (specifically, I would like to use Java)? I have some Clojure code running on Storm from which I would like to submit tasks to be executed in Python on other machines. Do you know if this is possible with celery? I couldn't really find any information on it.
[1] http://aws.amazon.com/sqs/faqs/#How_many_times_will_I_receiv...