PS: Just a guess. Maybe a timeout? On Arch Linux, if I start Evolution and retrieve emails close to the login, I don't need to give a password for the gnome keyring thingy, but if I wait a few minutes before I retrieve emails for the first time after a login, I need to provide the password.