(X)HTML+CSSで書いている場合は特にそうなんですが、HTMLでの要素の出現順序と見た感じの出現順序がずれているということは良くあることだと思います。floatやposition:absolute;を使用している場合などはありがちですね。
そういうサイトに限らず、Lynxやw3mなどのテキストブラウザやスクリーン・リーダなどでブラウズした場合、サイト・ナビゲーション部分がなかなかな出てこない、またはサイト・ナビゲーション部分が長くなかなか本文に到達できないということは良くあることなのかもしれません。それに対する解決法について、//hicksdesignのskip navigation solutionsで書かれてました。
このエントリは、The Web Standards ProjectのScreenreader Invisibilityから派生したものみたいで、上記の問題の解決法として比較的ポピュラーだった、display:none;で視覚系ブラウザからリンクを隠すという手法が、実はスクリーン・リーダからも隠されてしまうことがあるということを回避しようというものみたいです。
とはいうものの、現状でのLynxやw3mなどのテキストブラウザやスクリーン・リーダなどのCSS実装状況を逆手にとったも解決法なので、これも将来に渡って通用することは保証されないでしょうね。こういったことに配慮するのならば、すべてのブラウザでサイト・ナビゲーション部分または本文へジャンプするアンカー表示させるべきなのかもしれません。