Certificate Authorities
The email client would automatically look up the PGP key of all receivers in key stores (first local, then public keyservers, ideally provided by the receiving email provider) and encrypt the mail with these keys. Ideally, we would use trusted keys by regular PGP standards. However, we would fall back to any suitable key with less trust, down to a complete unknown key if required.
This is a horribly bad idea. Everyone can generate keys for every mail address. Without any trust path, you have no chance to decide which one is the right key. Instead of further argumentation, have a look at the key server results for president@whitehouse.gov. Don't expect any of them to belong to who they claim to be.
On the sending side, any email client would automatically create a PGP key locally and publish the public key part on the email provider's keyserver.
Now we're getting on a more reasonable path. But: This somewhat counterfeits the idea behind OpenPGP. Trust is not defined by on which key server is stored, but what keys are trusted. You're looking for a certification authority (yes, in the end pretty much the same thing like X.509 uses). There are already some in the OpenPGP world, have a look at CAcert.
Your provider could also be a certificate authority (to some degree, you're already trusting him anyway). To do so, you would both sign and (fully) trust his certificate authority key, in return he's signing all keys generated for his own users. OpenPGP can do all this out of the box; no need to change it. You just need to make people understand and implement it.
An Automated Web of Trust
The only "new" idea here would be to automatically manage trust by exploiting social assumptions. The main assumption would be that two parties continuously exchanging emails somehow know each other and can identify each other by the contents of the mails exchanged. With each email exchange, the email clients of both parties would increase their internal trust score for the other party's key. This internal trust score would be applied like traditional Web-of-Trust confidence levels to build up an automated Web-of-Trust.
Now we're getting to a completely different concept, which is already known as certificate pinning (but I haven't heard of it being implemented for OpenPGP).
Yes, this might be reasonable for people you already had contact with. But it makes things much more complicated, especially regarding computation of trust. This would require a probabilistic computation of trust to be able to deal with the large number of rather low trust issued by such a system, like proposed by Maurer et al. in 1996: Modeling a public-key infrastructure; maybe together with automated issuance of trust.
Conclusion
Your first proposal, providers acting as certificate authorities has indeed some charm, is compatible with OpenPGP and rather easy to implement. I'm not sure if Google even has similar plans for its End to End project.
For me, this seems like a suitable approach for the public part of the key management issue. It does not solve the private part (e. g. getting the private key to all mobile devices). We also inherit all known issues of PGP.
Probabilistic models have already been proposed nearly twenty years ago, there just was nobody to pick them up. If you scroll through the citations for the paper linked above, it even seems quite a bunch of publications claim to have solutions for your proposal. One large problem is, this wouldn't be compatible with OpenPGP (as defined by RFC 4880) any more, and introducing new systems in a way they get acceptance isn't very easy. Furthermore, it's even harder to understand what's going on in probabilistic models.
Another thing is you'd still have to teach people on how to use OpenPGP and understand the Web of Trust concept. This is no technical problem (although it might be more complicated than necessary); there is no plain technical solution for security. Don't just make people assume their communication is secure when they're not able to understand what's going on, bad things happen if people do so, or a horrible bunch of dismissed, non-revoked keys on the key servers.
Further Notes
- The internal trust score needs to be very fine-grained in order to allow automated increments and calculation (e. g. 0..1 range with IEEE-754 double precision).
Off topic regarding what's really discussed in this Q&A, but anyway: this is no reasonable use case for floating-point values. Floating point numbers have high resolution around 0, but this degrades quickly when going towards larger values (I was told you can observe this in Minecraft, where some funny jumps occur when you get near the borders of the world). Why not just map it to the whole 64 bit integer (32 bit probably would be more than fine, too) which occupies the same space, but with a constant resolution of all values. Using floating-point variables you'd have to limit yourself to a very small value range (0..1 would probably be fine, but still then you have to deal with funny effects not too important for probabilistic calculation and waste some memory and computational power.
