SJISの場合(WindowsのDBCSの場合)、最長で2バイトなので、
ByteTypeの結果「Lead or Trail or 1バイト文字」が一致して、コードそのものも一致すれば、
次の文字のByteTypeの結果も一致します。

ここまでOK？
ということで、

>S1のS1IndexとS2のS2Indexに対してByteTypeを調べれば
>それでいいのかな？

はTrueです。
しかし、この方法だと、検索を進めるたびに毎回ByteTypeが実行され手間です。
ならば、最初から2バイト文字を切らなければいい、という話になり、

>for i := Index to EndIndex-Length(SubStr)+1 do
>begin

を、例えば、

i = Index;
while I <= EndIndex - Length(SubStr) + 1 do
begin
　…
　if S[I] in LeadBytes then Inc(I);
　Inc(I);
end;

として、Trailからの比較を避けてやるわけです。

…これがわかんないって…今までRLEとか可変長データとか使ったこと無いとか？まさか。