You could always try changing the address that your SEGA ID is linked to. There were some people who have been having problems because the email provider was just not receiving the mail when it was sent to their account.
The email you are looking out for is from
[email protected] and has the title
【PSO2】Eメール認証手続きのお知らせ
and the body
本メールは『ファンタシースターオンライン 2』の認証メールです。
下記のEメール認証コードをゲーム画面に表示されているテキストボックスに入力して、
ログイン手続きを進めてください。
<8 character code here>
※ご注意
本メールは送信専用となっているため、返信いただいてもご回答することが
できません。
ご不明な点がある場合や、本メールに心当たりがない場合などは、お手数ですが、
公式サイト内にあるお問い合わせ窓口よりご連絡いただきますようお願いいたします。
『ファンタシースターオンライン 2』公式サイト
http://pso2.jp/
―――――――――――――――――――――――――――――
株式会社セガ 『ファンタシースターオンライン 2』運営チーム
―――――――――――――――――――――――――――――
If you don't have that, go to any of your other mails from SEGA and look near the bottom. There should be a SEGA ID link which goes to cha.isao.net. You can go there, log in and find your profile information (should be the first link near the top) and then you can change your email address from there.
If you do that, try re-sending the key again and see if that succeeds.