NHKのチコチャンで「さいとう」さんをやっていました。私も以前から色々な漢字の「さいとう」さんがいて、（苗字の漢字を間違えると失礼だと思い、結構神経を使わなくてはいけないので）面倒くさいなと思っていました。

番組の要点を書いておきます。
１．現在「さいとう」さんは約８０万人いて、戸籍に使われている（さいとうの）「さい」の漢字は５９種類。

「さいとう」さんの起源
２．（平安時代）藤原氏が栄え、宮中（国の役所）は藤原だらけになる。

３．齋宮の長（齋宮頭：さいくうのかみ）だった藤原さん（藤原叙用：のぶもち）が、藤原の混乱を避けるため、齋宮頭と藤原を組み合わせて斎藤と名乗った。
（この流れで、武者所の藤原は武藤、伊勢の藤原は伊藤、内舎人（うどねり）の藤原は内藤、などと名乗るようになる）

４．（江戸時代から多くの人は苗字を持っていたが）明治8年、「平民苗字必称義務令」が出され、役所に苗字を紙に書いて提出することななった。（当時、漢字慣れしていない人が多くいて）適当な漢字を書いて出した人や、役所での誤字などがあり、色々な「さいとう」さんが生まれることとなる。

５．苗字の起源となった齋宮から言うと「齋藤」が正しいが、一斉（いっせい）の「斉（そろう、とい意味）」が、複雑な「齋」に形が似ていることから（略字、当て字、として）斉藤が多く使われるようになった。

＝＝
齋宮とは：
（平安時代）伊勢神宮の近くに有った齋宮が有った。ここには、天照大神（あまてらすおおみかみ）に仕える齋王（皇族の未婚の女性）がいて、この齋王に仕える一番偉い役職が齋宮頭。（源氏物語を読むと、齋宮が重要な場所であることが良く分かる）
「齋」には、神仏を祀る時、心身を清める、という意味がある。