I don't know about the NSA, but I've personally negotiated a deal with a CA to add whatever domains we wanted to a certificate without validation. They just "trusted us."