While we can import other people's public keys manually, it would be much less hassle to just import them from public key servers if they have a key listed in one. Just searching them for the mail address shouldn't be hard to implement, and from that point on it'd be the same as if the key was attached to the mail (asking wether the key should be trusted, then import)