A very convenient place to store and retrieve them is under a "passwords" folder in your private mail account or your Dropbox, both of which get synchronized with your unprotected smartphone...

Draconian password schemes lead to really insecure user behavior. For example, an iTunes account requires upper-case, lower-case, and a number; but it doesn't tell you that until you try "insecure" passwords. So I bet a lot of users, feeling really frustrated, just use their name (capitalized), and birthday, rather than the semi-secure password the they wanted to use (or in my case, a fairly strong pass-phrase with no numbers).