The good thing is that now Gmail's IMAP supports OAuth, so people migh be much less reluctant to give you access to their mailboxes.

Yes, the nuisance is there, but I'm sure there is a way to solve it. The good part is that it does not make the service unusable, so, people can start using the service even though with this nuisance.

Release early and then iterate. ;-)