producing GnuPG keys as proof of work

[Mirimir]

Would it be feasible to use gpg in batch mode to generate numerous keys,
selecting for a particular key ID, or perhaps a longer part of the
fingerprint? I'm aware of shortcuts for creating keys with arbitrary key
IDs, but they produce keys with atypical key lengths etc. Based on
limited experience, I suspect that entropy would be the limiting
resource. Is that correct?

I imagine that websites could provide random alphanumeric strings to new
users, and require them to generate functional GnuPG keys (with normal
key length etc) with fingerprints that begin with the specified strings.
Having accomplished that, new users could edit their key, and specify an
account name and email address.

Is there an existing app or script that does this? Neither marc.info or
Google has led me to one.