日本語は同じように読み、同じように使うのに意味が違う言葉が多くて難しい！
その一番の例が「始めまして」なのか「初めまして」なのかどっちだろうという疑問です。
字義通りに解釈すれば始は開始、つまりスタートの意味ですね。
エンドとスタートの対応関係で物事の起こりを意味します。
初は最初のようにファーストの意味で時間的な意味です。
はじめましてが「はじめて会う」という意味ならfor the first timeですから
やはり「初めまして」が正しいように思います。
もちろんこのレベルで言葉を使い分けている人なんてほとんど居ませんが。
「初対面」という言葉と関連させて理解するとよいかなと。