How to exchange a secret through untrusted server in two steps?
Without changing an assumption somewhere, it does not look possible.

Here is what your ideal protocol would look like:


Alice sends the invitation to the server (to pass along to Bob), along with a message that is encrypted somehow, but not bound to Bob (as Alice doesn't have anything from Bob to distinguish him from anyone else)
Bob gets the invitation, and the encrypted message, and somehow (without any further interaction from Alice) decrypts the message


The problem is with step two; if Bob can decrypt the message, why can't anyone else (in particular, why can't the server)?  The server knows everything that Alice knows about Bob, and so the server can perform the decryption operation just as well as Bob can.

Now, a similar problem lies in the original protocol; when Alice downloads Bob's public key, the server could provide his own (and when Alice uploads the encrypted message, the server decrypts it, and reencrypts it with Bob's public key).  You did say that the 'untrusted' server can be trusted not to do this.

Obvious ways to address this:


Change the trust assumption; you already trust the server to be honest about public keys; also trust the server not to be malicious about reading intermediate mail (and with this assumption; Alice can encrypt the message with the server's public key, and have the server reencrypt it with Bob's when he downloads it).
Give Alice something from Bob (even a symmetric key) that the server doesn't know.