進行度はキャラ毎の管理で、ムービーの判定基準はアカウントないしクライアントだから、
判定出来ないんですかね？
キャラ選択画面前のムービーの時点でキャラを全部精査して進行度を把握するか、
新しくムービー用にアカウント単位で進行度を管理するスペースを作る必要がありそうな気がしますし。
これが出来れば初心者じゃない新規キャラにまで初心者マーク付く問題も解決できそうですがそれはともかく。

ローカル側の設定ファイルにムービーの基準値を保存できないですかね。
初期値が新生編でどれかのキャラの進行に合わせて更新して提案を実現したり。
更新のタイミングはログイン時でいいと思いますが。

まぁ原因の方は憶測になるんでこれでいけるのかは知らないですが、
キャラ全精査が出来ないならそんなでどうでしょう。