Skip,
I favor the implicit approach.
Existing DNs schemas have tremendous inertia, and in addition to more intellectual reasons, registering existing country-based DNs within DNS is overwhelmingly the path of least resistance. In order to support Internet directory interoperability, it is far easier to say (to the DoD PKI, for example):
"You have to register a DNS record for OU=DoD."
rather than:
"You have to change all of your certificates and directories to include a new top-level RDN."
I agree with Bob's goal of eliminating the need to pass certs in session handshakes and messages. If there were only two options (change the DN or add an extension), then only the first moves toward that goal. But you have proposed a third option: leave the cert alone! For my part, I am simply in awe of the elegance of that approach. It might even work.