The first architecture using two ELBs has a long list of cons, most of which are solved by using HAProxy as your internal load balancer. May want to considering adding that as another option on the matrix.
Really nice write up. I'm curious if you guys have done any extensive throughput and latency benchmarking? I saw the note saying "ballpark figures."<p>FWIW, I've been working on a framework for empirically testing queue performance for scaled-up, distributed deployments (<a href="https://github.com/tylertreat/Flotilla" rel="nofollow">https://github.com/tylertreat/Flotilla</a>). Haven't gotten around to adding support for AWS services yet, but would be interesting to see how they compare.
You give Redis a yellow rating on prioritization, noting that this can be partially achieved using multiple lists. Wouldn't it be much better to take advantage of Redis's sorted set type?
Surprised they didn't mention IronMQ: <a href="http://www.iron.io/mq" rel="nofollow">http://www.iron.io/mq</a><p>It's not perfect but pretty damn close. And it run on AWS et al.