Sean:
A receiving agent SHOULD be able to verify signatures with keys of any size over 512 bits.
This is asking for denial of service attack. What if someone sends a certificate that contains a 64Kbit value claiming to be a public key and a blob of random bits claiming to be a signature? The amount of time to check the signature (and probably find that it is not valid) is onerous.
Today, I cannot imagine someone making use of a public key larger than 8192 bits. Double that it you want to be very future proof.
Russ