2ch形式っぽいのも良いかもしれない。

■今の状態のBBSが表示してるスレッド一覧は、
そのページのスレッド一覧で、
1ページNスレまでと制限付けておいてページを分ける。
(<<前のN件、次のN件>> みたいなナビゲーションで)

■スレッド一覧のページを別に作って、
100件ずつとかでスレッドタイトルを羅列して表示する。
100件を超えると、ページを分けて、前の100件、次の100件とかにしたり。

■レスが多くなると一つのスレがやたら長くなるので、レス数を制限(2chみたいに)。
デフォの状態で表示される1スレあたりのレスは最新の10件とかにしておいて、
[全てのレスを表示]とかで、そのスレ全体を別ページで表示させるとか。

■検索についてはあってもなくてもいいような気がするんだけど
どんなのにすると良いのか難しい所…。
結局どれについても複雑に絡み合って難しいんだが。
検索についてはあまりイメージが沸かないがレッツPHPの
http://php.s3.to/pppbbs.php?mode=search こんなのとかがあったりするね。
まぁなくてもいいような気はする…。

■全ての書き込みにid・ナンバーがあるが、スレ自身にid・ナンバーをつけて
レスは単純に1〜とするというのもあるが…。何が都合がいいのかは私には解らない…。

■返信フォームの「Subject」に「Re:返信対象のタイトル」等と自動的に入れておけば
レスのタイトルがタイトル無しだらけでパッと見何のスレのレスか解らなくなる事もないかも。
value=""とかに突っ込むんかな？

今すぐにぱっと思いついたのはこんな感じです。