[vacri]

I haven't used kinesis myself, I've just heard that it's "SQS with the FIFO issue fixed", and wondered if it might also be suitable for you. Judging from the other comments, it wouldn't be a silver bullet, though.

[vacri]

Speak of the devil - I've just had to create a new SQS queue just now (first time in months), and there's an option to make it FIFO.