いわゆるK6対策のパッチ（MS配布パッチとK6-2PAT）はWindows95での350MHz以上のK6系CPUを搭載した場合に発生する、起動中にタイミングを調整する為の演算が速く終わりすぎることによるWindows保護エラーを出るのを防ぐものであり、決してWindows全体を安定させるとかそういうものではありません。N3は何度も話題に出ていますが、HXマシンorVXマシンではどうしても安定しないことがあるので、その場合はすっぱりあきらめるしかありません。N3で安定しないとなると、500MHz動作させたいのならば、N4下駄を手に入れて試すしかないのでは？

CPUが500MHzで回らないだけです。

400MHzで安定しているというのは、N3を使用して66*1.5*4ということですか？
それなら冷却をきちんとすれば、66*1.5*5も通る可能性はあると思います。
ヒートシンク／ファンは何をお使いで、どのように固定されていますか？

返信ありがとうございます。

サンヨー電気のクーラー(ヒートシンクは付属の物を使用)を熱伝導シートで留めています。

たまに450MHzで起動が出来なかったりすることは冷却不足と考えていいのでしょうか。

寒い日の朝に電源を入れて、いきなり起動失敗するようでしたら冷却不足ではないでしょう。
起動して１０分後にハング、再起動すると今度は５分後にハング、次は２分後・・・てな感じで、
熱が蓄積するにつれて短いサイクルでハングするのが冷却不足の典型パターンです。
全くランダムに止まるのであれば、ノイズや電圧などの別要因が怪しいです。