Проблема такая: нужно реализовать табличку. В ней две колонки - в первой QCheckBox, во второй - QLabel с форматированным текстом. Строчек таких может быть около 1000. Еще к этой табличке прикручен поиск - при вводе лишние объекты скрываются (через hide()) либо наоборот отображаются обратно.
 
Сначала я реализовал это через QTableWidget - все нормально, одна проблема: прокрутка страшно тормозит.

Потом я это реализовал как комбинацию QScrollArea+QWidget+QGridLayout, скроллинг стал работать идеально, но взамен получил страшные тормоза при подгрузке объектов (т.е. на label->setVisible(true) и layout->addWidget()) - когда виджет внутри QScrollArea начинает растягиваться, элементы плющатся, и программа коматозит достаточно долго.

Как это следует делать нормально? И возможно ли это вообще?
P.S. Использую Qt 4.2.3, Linux

Да. Нужно использовать model/view/delegate

Делай как сказал Gryz, если нужен не плаин текст используй QItemDelegate в котором переопредели drawDisplay где за рисование текста у тебя будет отвечать что-то типа QAbstractTextDocumentLayout. Для оптимизации вывода при скроллинге можно использовать таймаут, разделяешь на временные промежутки: средняя скорость (~ половине частоты восп. глаза), быстрая (при этом можно выводить только первую строку, чтобы пользователь мог ориентироваться), очень быстрая, ничего не выводить. Хорошо еще при этом показывать индексацию в виде тултипа возле скроллбара.