There is actually something _else_ they could do; run a service where you forward your email to an address on their end (with GMail's autoforward thing or whatever); they push notifications to you based on that. Of course, that would require server infrastructure, and there'd still be privacy concerns (though lesser ones, as they wouldn't have to _store_ anything).