Jared has writed another amazing post about Autolayout. AutoLayout Myths, Table View Performance, and Side-by-Side iPad App Multi-tasking.
After reading it I think that it's not autolayout job to solve all of our problems but to be a way of solve the layout of our views, and only that. Although is totally fine to make public some of it's worst case scenarios.
In fact I had to solve this same issue recently while working on the next version of the WorkAngel App. We have a table view with a bunch of different kind of cells with a complicated layout. It was really nice on the simulator and on the iPhone 5 but we had a lot of problems to make it fast on an 4S.
I really hope that Apple polishes the estimatedRowHeight API because, as Jared mention, it has a lot of problems. I've seen crazy visual glitches while trying to add rows with a fetched results controller.
At the end we had to take the cache approach. Precalculate the height of the rows so when the tableView needs the height it will be really fast.
For me is one of those cases where Apple could do something more to help us, but we will see ^^