Embedding POW in an EC public key
I like the features of the second, except for some drawbacks:


I don't believe the drawbacks are as bad as you think.


  1.This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys.


It doesn't help the attacker; if the attacker sees the public key, the knowledge that the hash is small doesn't help him (as he sees the exact value).  And the additional hashing requirement doesn't help Pollard Rho or Big-Step-Little-Step (two algorithms for computing discrete logs)


  2.This relies on the point addition algorithm being highly efficient, and assumes an attacker may not have some new and better way to perform this operation.


I believe that's a fairly safe assumption; it's hard to see how someone could generate $(x, xG)$ pairs in a manner that is significantly more efficient than your algorithm.  In any case, the most significant threat is an attacker with a bot or DSP farm; that would allow him to generate a number of public keys considerably faster than an honest user.


  3.It's possible that an unprivileged attacker observing the initial POW generation could determine some information about the key.


With your algorithm, the attacker has no knowledge of where you started the search.  If he learns that you took a while, he can deduce that a $(x - \delta)G$ doesn't meet the hashing criteria for a number of $\delta$s, however, as he can see the value $xG$, he could verify that directly if he wanted to, and so it doesn't actually leak any information about the private key.

So, it looks safe; my only concern is that it might not provide as much DoS protection as you hoped (of course, I don't know how much protection you're looking for, and what assumptions you are willing to make about attacker capabilities...)