If your job is easily parallelizable then you can run multiple lambdas in parallel. For the above use case they probably should have kicked off one lambda per prefix or similar.
We considered it, but at the time we just felt implementing map/reduce over Lambda would just introduce a more complex architecture for such a simple problem.
Maybe the recently introduced SQS->Lambda support might make it a bit cleaner, but in the end we opted for EC2.
The problem was the task just couldn't complete in < 5 minutes.