The basic idea of public key is to be visible to everybody. I consider the real problem to be "spamming." If you have some site which stores the keys and it has a thousand of different public keys claiming to be from, e.g. "Laura Poitras" you don't know which one is the real one. So the selection of the "real" key between of all of possible keys is something that should be verified independently. Even if you have only one key, you must verify that really that key belongs to the person you want to reach.
Snowden solved it by requesting the public tweet of Lauras's key fingerprint which was enough. Having the match of the fingerprint is enough. It's much smaller than the whole key. For example, if Laura's key is 4096 bits to print it you'd need around 700 letters. But to verify some 4096 bits you have to actually be Laura's key, it's enough that the fingerprint of, for example, 160 bits match: the math magic involved in creating the fingerprint should guarantee you that nobody can create another key and have the same fingerprint.
In the article, the fingerprint used 4 bits per letter, and there were 40 letters, so it was just 160 bits that Snowden used to verify the key.