Actually someone has already published an intentionally created 64 bit
keyid collision. Presumably he did in fact generate about 2^32 keys.
It is made easier by the fact that generating a DSS key is just a matter
of doing g^x mod p for a bunch of different x's. So in fact you can generate
a series of keys simply by repeatedly multiplying g^x by g to get g^(x+1).
The hash which generates the keyid has the same prefix and so only the
g^x part varies, making the search exceptionally fast.
This will not allow you to make a keyid which matches someone else's, as
that is 2^64 work, a whole nother kettle of fish. But generating pairs
which have the same 64 bit keyid is very tractable.
Hal