サーバー混雑時はコンタクトリストが正しく表示されないようです。
通常は、双方でコンタクトリストに登録した場合は相手のオンライン状態を知ることができますが、サーバー側の同期状態が悪化した場合はほとんどコンタクトリストが使い物になりません。
同一サーバーであれば、正しく表示されることが期待できますが、絶対ではないようです。
コンタクトリストに登録した相手がコンタクトリストから削除したためオンライン状態が表示されなくなったと勘違いしやすいです。
経験的に、サーバートラブル中にログインできたとしてもコンタクトリストが一部しか表示されなかったり、全くなくなってしまうことがあります。
気にせず遊んでもかまいませんし、サーバーが安定するまで待ってからKaiEngineを一旦終了してログインしなおすと表示されるようになるでしょう。
別の手段（メッセンジャーやSkypeなど）で連絡を行って相手もログインしているはずなのにコンタクトリストの相手がオンラインにならない場合が多々あります。
おそらく、今ログインしているOrb.サーバーが相手と異なっている場合で、サーバー間の同期が崩れている場合はまずまともに表示されません。
サーバーが安定するまで待つ事以外には決定的な解決方法はありません。
即時解決方法としては同一サーバーにログインできるまで何度かKaiの再起動をおこなえば表示されるようになることが期待できますが、サーバーがこの状態に陥っている場合は安定するまでサーバーの再起動が行われるようになるのでゲームもまともに遊べない状態になっているはずです。