What's wrong with Registry.GetValue?

The problem is that you probably are compiling the solution as x86, if you compile as x64 you can read the values.

Try the following code compiling as x86 and x64:

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("MachineGUID:" + MachineGUID);

        Console.ReadKey();
    }

    public static string MachineGUID
    {
        get
        {
            Guid guidMachineGUID;
            if (Microsoft.Win32.Registry.LocalMachine.OpenSubKey("SOFTWARE\\Microsoft\\Cryptography") != null)
            {
                if (Microsoft.Win32.Registry.LocalMachine.OpenSubKey("SOFTWARE\\Microsoft\\Cryptography").GetValue("MachineGuid") != null)
                {
                    guidMachineGUID = new Guid(Microsoft.Win32.Registry.LocalMachine.OpenSubKey("SOFTWARE\\Microsoft\\Cryptography").GetValue("MachineGuid").ToString());
                    return guidMachineGUID.ToString();
                }
            }
            return null;
        }
    }
}

You can read more about Accessing an Alternate Registry View.

You can found in here a way of reading values in x86 and x64.

It probably has to do with UAC (User Account Control). The extra layer of protection for Windows Vista and Windows 7.

You'll need to request permissions to the registry.

EDIT: Your code right now:

var keys = Registry.LocalMachine.OpenSubKey("SOFTWARE")
    .OpenSubKey("Microsoft")
    .OpenSubKey("Cryptography", RegistryKeyPermissionCheck.ReadSubTree)
    .GetValueNames();

Only requests the permissions on the Cryptography subkey, maybe that causes the problem (at least I had that once), so the new code would then be:

var keys = Registry.LocalMachine.OpenSubKey("SOFTWARE", RegistryKeyPermissionCheck.ReadSubTree)
    .OpenSubKey("Microsoft", RegistryKeyPermissionCheck.ReadSubTree)
    .OpenSubKey("Cryptography", RegistryKeyPermissionCheck.ReadSubTree)
    .GetValueNames();

EDIT2:
I attached the debugger to it, on this code:

var key1 = Registry.LocalMachine.OpenSubKey("SOFTWARE", RegistryKeyPermissionCheck.ReadSubTree);
var key2 = key1.OpenSubKey("Microsoft", RegistryKeyPermissionCheck.ReadSubTree);
var key3 = key2.OpenSubKey("Cryptography", RegistryKeyPermissionCheck.ReadSubTree);
var key4 = key3.GetValueNames();

It turns out, you can read that specific value, at least that's my guess, because all data is correct, until I open key3, there the ValueCount is zero, instead of the expected 1.

I think it's a special value that's protected.

You say you're on 64-bit Windows: is your app 32-bit? If so it's probably being affected by registry redirection and is looking at HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\Cryptography. You may have to P/Invoke to work around it: http://msdn.microsoft.com/en-us/library/aa384129.aspx.