漢字で姓・名を登録すると、正しく並び替えてくれなくて、ほんま不便ですね、あれって。
OEの並び替えは、実際には漢字表示の漢字の文字コード順で整列されます。本当はよみがなの欄で、ただしい読みを指定しないと、OEのアドレス帳みたいになります。これはWordやExcelなどで住所録を作るときにも重要なことで、日本語で並び替えをするときに、よみがなの情報がないと正しく並び替えはできません。
でもOEって元は本家のOulook 97&98のフリーソフトバージョンみたいなものだから、その辺の機能にケチはつけられませんね。

ちなみに私のメールデータを破壊してくれた次期のOE5のアドレス帳は、よみがな(ルビ)の欄があります。ちゃんとよみがなを入力すれば、正しく並び替えしてくれます。

解決策についてですが、姓名の欄にひらがなで名前を入力するのはどうでしょうか？
私は昔はローマ字で管理していましたが、最近は並び替えについてこだわらなくなったので、漢字でアドレス帳に登録することもあります。実はアドレス帳もあまり使わなくなりました。OEはメールアドレスの頭の部分やアドレス帳の名前を途中まで入力すると、その語尾を補完してくれる機能(オートコンプリート)があり、これが結構便利で作業効率もいいです。記憶力も養えます。宛先の欄に直接キーボードからタイプすれば補完してくれます。