"Technically your email client will automatically prepare for this by creating a crypto key for you and uploading it to your provider (or second best to public keyservers)."

This seems like a good way to flood key servers with multiple keys for the same address, making an attempt to find the right one very difficult. Average users are going to end up having one key per device, or more depending on how many times they end up wiping the device and reinstalling.