相手がキーに新しいメールアドレスを追加したら(>>26 の方法で）、
新しいメールアドレスの公開鍵を送ってもらわないと
新しいメールアドレス宛に暗号文を送れないのでしょうか？

それとも他の方法がありますでしょうか？
新しいメールアドレスを追加する前の古いメールアドレスの公開鍵はもっています。