Дело в том, что эта фича была в спецификации с конца 90-х, уважающие себя вебмастера, верстальщики и прочие сайтостроители, читающие стандарты, книжки, спецификации, рекомендации и прочую занятную литературу вроде статей и обзоров, о подобных вещах знали уже тогда. Другое дело, поддержка фич браузерами. Недобраузер IE, традиционно не поддерживающий или по-своему интерпретирующий половину фич современного веба, вроде до сих пор про link тэг не знает. В Opera полноценная поддержки появилась в ноябре 2002, в Mozilla в октябре 2001. Собственно, я-то эту вещь именно в тогдашней Mozilla впервые увидел...
Так что и получается, что фича вроде как давно есть, браузеры ее поддерживать начали несколько позже, а недобраузеры как не поддерживали, так и не поддерживают. А посколько бОльшая часть сайтов затачивается исключительно под недобраузеры, про навигацию средствами html вебмастера и вовсе забыли. Сверстают нав. меню и успокоятся, вместо того, чтобы грамотно продублировать его link-тэгами.
Для полного счастья еще и из firefox на каком-то этапе эту вещь выкинули (или даже изначально ампутировали, когда mozilla пилить-точить начали). Сейчас, скорее всего, оно в виде какого-нибудь расширения существует.
Что касается сайта Opera - сверстан профессионально (даже валидацию xhtml 1.0 strict проходит, гыгы :]), так что неудивительно, что про navbar они не забыли. В онлайн-хелпе Оперы навигация, кстати, тоже активно используется.