The processing of my job might have a legit Lambda timeout of 5 minutes, because occasional proper evaluations take that amount of time (even though most take much less).

In my opinion, the fact that the SQS connector can't keep hold of that message after receiving a 429 response (while keeping the visibility state updated, that is something we were doing ourselves prior to this migration), and process it right away after capacity has been freed up, is a flaw.

There's a 5 minute waiting time for the retry in this scenario that needn't be there, even if the lack of it would force the SQS connector to be slightly (but just slightly) more stateful.