Perhaps I'm assuming too much, but it looks like you might be confusing notification with queueing. As you found with SQS, queueing systems can make for poor notification mechanisms. Did you try using AWS SNS (http://aws.amazon.com/sns/) for your first two use cases? We have similar notification use-cases internally, and SNS has worked great.