原です。

正規表現が空にマッチする時、最長条件が守られていないように
見えます。

print "abc".sub(/b?|b/){ "(#$&)" }, "\n"  # => (a)bc
print "abc".sub(/c?|b/){ "(#$&)" }, "\n"  # => ()abc

b?|b の表す文字集合より c?|b の表す文字集合の方が大きいのに前者
の方が、マッチする文字列が長い。

でもこれはなかなか微妙な仕様なのかもしれません。
---===-=-=-=-=-=-=-=-=======--=-=-=-==-=-===-=-=-=-=-=-=--=-==-=--
　　                         Shin-ichro Hara(Nagaoka Univ.of Tech.)