I think it's important to use the same exception type for all of the various failure modes here.  In the C OpenSSL API, applications need to separately handle the ```!HAS_EC``` case, the unknown ```sn``` case, and a failure from ```EC_KEY_new_by_curve_name```, since any of them are possible, even for the same input, depending on OpenSSL version, compile options, and distro patches.

As a concrete example, an application trying to use a Brainpool curve will get an ```sn2nid``` failure on OpenSSL 1.0.1, an ```EC_KEY_new_by_curve_name``` failure on Fedora and RHEL (presumably), and a ```!HAS_EC``` failure if ```!HAS_EC```.

This sucks.  At the end of the day, users should only care whether their combination of pyOpenSSL and OpenSSL can or cannot use the requested curve.  So a single exception type should IMO be used for all three error paths.

That being said, I see no fundamental reason why ```NotImplementedError``` is worse than ```ValueError``` -- I think think that ```ValueError``` is a common and expected error type for a function parameter having the wrong value.