小弟也用過512k的Tualatin，不過也是1.26GHz的，同樣是Asus主機板，不過是Intel晶片組，
印象中POST時應該會顯示出Intel Pentium III-S 1266MHz，
只要POST對CPU的辨識正確，就是支援了，
印象中當時要是主機板要是不能援新CPU，多半連POST都看不到，CPU就被瞬殺了；
或是主機板可以跑，BIOS不認識新CPU，則會出現類似CPU microcode error的情況，
要是您以上都沒遇到，且還能進系統，應該就是板子跟BIOS都ok了，
雖然去Asus官網看，他們會說Pentium III-S僅適用於Sever主機板，
但小弟也一樣把它裝在DT上跑了幾年。

至於您要重新啟動數次才能進OS，或許是有些零件老化了，送去修修看吧，
不過不知道您有沒有安裝其他PCI介面卡？這張主機板用的南橋應該是VT82C686B，
這南橋有個出名的bug，就是高載時會導致系統不穩定、關機或重啟，所以要是有裝其他PCI卡的話，
可以把它們移除後再試試。