まさか Add するたびに BeginUpdate と EndUpdate 呼び出したりしてないだろうな？
あとは別スレッドってどう実装させてるかが分からんことには。
2005 なら BackgroundWorker マジお勧め。