перемешивание следствие распределённости системы, но странно при этом, что они пишут «Amazon SQS makes a best effort to preserve order in messages...» (http://aws.amazon.com/articles/Amazon-SQS/1343#03).
Прочитав о том, что они стараются сохранять порядок сообщений я всё же надеялся на другие результаты
сложно сказать, по крайней мере это не оговаривается, у меня в тестах больше 10 секунд не получалось, но возможно при каких-то условиях можно получить больше
Тестирование Amazon SQS