As with all other parts of the bloatware known as "Gnome" Evolution cannot figure out the difference between a network failure and an Authentication Failure.  The upshot: when one tethers one's computer to one's cellphone, NetworkManager (a completely undocumented and notoriously buggy part of "Gnome") is not involved in any way -- it simply doesn't understand modem tethering.  So, Evolution boots up in an offline mode (little icon in the lower left is "unplugged") and since it doesn't understand that network connectivity is not being served up by the mysterious and largely useless NetworkManager, it starts asking for passwords.  Unfortunately, once this has happened, even though every single time a password has ever been entered into Evoultion the "Remember this Password" box has been checked, from that time forward, regardless of what network interface is available upon the next email check, it prompts for a password!  There is no value in having Evolution imply that it will "remember" passwords if it consistently "forgets" them.  Somebody please grow a spine, and figure out how to use the network layer of Linux, which has been stable for some twelve years, and understand that NetworkManager is not the Linux network stack.  Please stop relying on buggy beta-level software, or at the very least figure out how to distinguish between a NetworkManager failure and a real Authentication Failure.  Email has been around a long, long time.  The protocols are well documented.  NetworkManager has been around for a very short time, and will probably die an ignominious death in the near future.  Don't tie a moderately useful product's (Evolution's) functionality to a "best-effort" experimental product's (NetworkManager's) functionality.