とりあえず，~/.gnome2/keyrings にある *.keyling を削除してみて下さい。

なお，初回起動時のEvolution設定アシスタントでのパスワードの保存は，３ヶ所あります。一度，アカウントを削除して，下記の部分でパスワードの保存を設定しなおしてみてはいかがでしょうか？

１.メールの受信
「パスワードを記憶する」にチェックを入れる。

２.メールの送信
「パスワードを記憶する」にチェックを入れる。

３.初回受信時のサーバへのアクセス認証
「このパスワードを記憶する」にチェックを入れる。

これで，毎回パスワードを要求されることはなくなると思います。

hardy で fix された古い bug とのことですが，
https://bugs.launchpad.net/ubuntu/+source/evolution/+bug/51500
は関係無いでしょうか？

seahorse(アプリケーション > アクセサリ > パスワードと暗号鍵）がインストールされていない
もしくは
seahorse-agent が起動していない
とか？

ちなみに「パスワードと暗号鍵」 -> 「パスワード」タブ -> フォルダアイコン(実はキーリング)を右クリックで，
キーリングのロック，アンロック，デフォルトへの設定などができる様ですが，Evolution を使っていませんし，
試しにロックしてみたものの(此方では最初アンロック状態でした)
何か効果が有ったのか無かったのか分かりませんでした．