Since July 2010 Ubuntu has disabled support for SSLv2 in OpenSSL library. If you are testing remote hosts for SSLv2 using a client that does not support it, you are getting false negatives.
Here is how you can check if you system supports SSLv2:
alla@notsoshiny:~$ socat OPENSSL-LISTEN:1080,method=SSLv2,cert=cert.pem,verify=0 READLINE
cert.pem has to be a valid certificate file that includes a private key. Generate one with OpenSSL if you don't have it.
If you get an error message saying "null ssl method", than you system does not support SSLv2. Go to When Distros Sneak Attack and read how to patch OpenSSL (or rather remove a patch) to support SSLv2 again.
If you get no error message, try connecting to your listener with openssl s_client and check that SSLv2 connection is established. If it works, you can proceed testing remote servers.
And while you are at it, have a look at sslcaudit - a wonderful tool for automated testing of SSL clients, that Alex has developed.