App is unable to write to the registry, even though the user has administrative privileges

Just because you're running as Administrator (or using an account with administrative privileges) does not mean that those administrative privileges are always in effect. This is a security measure, preventing malware from exploiting users who foolishly use their computer all the time with administrative privileges.

To wield your administrative privileges, you need to elevate the process. There are two ways to do this:

1. Use a manifest that indicates your application requires administrative privileges, and thus demand elevation at startup.

   This means your application will always run elevated and should only be used when your application needs this. The Windows Registry Editor (RegEdit), for example, does this, because there's little you can do there without administrative privileges.

   Find information about how to accomplish this here on MSDN, or in my answer here. Basically, you just want to add the following line to your manifest:

   <requestedExecutionLevel level="requireAdministrator" />
   

2. If you only need administrative privileges for certain tasks (i.e., saving a particular setting to the registry) and the rest of your application does not require it, you should launch a new elevated process to do this. There is no way to temporarily elevate the current process, so you actually need to spin off a new process.

   The advantage of this method is that your application does not have to run with administrative privileges all the time (which increases security), and that users who do not have administrative privileges will still be able to run your app to do everything else (i.e., everything but the one or two tasks that do require elevation).

   You spin off a separate process that contains only the logic needed to write to the registry using the Process class and request elevation for this process using the runas verb. For more information, see this question. I have also written an answer that provides a complete description how to accomplish this from C#, including sample code.

Of course, as other answers have mentioned, it is more likely that the design of your application is incorrect. The whole logic of the Windows security model is that regular applications to not require administrative privileges. They don't need to write to the registry or do other things that could potentially compromise the machine. If you need to persist settings, might I suggest two other possible approaches:

1. Recognizing that Windows is indeed a multi-user operating system and writing your settings only for the current user. This makes good sense anyway because different users often have different settings and preferences. Instead of the HKEY_LOCAL_MACHINE branch of the registry (which requires administrative privileges to access), you would want to use HKEY_CURRENT_USER. Change your first line of code to:

    RegistryKey softwareKey = Registry.CurrentUser.OpenSubKey("Software", true);
   

2. Skipping all of the hassle and complication of writing to the registry altogether by using logic built into .NET to persist your application's settings. Start reading the answers here, or here, or on MSDN to learn how to do that. I'd say that this is by far your best option. Don't write complicated code yourself to do something that the framework you use already has built-in support for doing with ease.

The design of your application is probably wrong. Standard desktop apps are not supposed to write to HKEY_LOCAL_MACHINE. Because of UAC, you need to have administrator rights, and be running in an elevated process in order to be able to write to HKLM.

If your application does need to make changes to HKLM then consider doing so at installation time because the installer will be run elevated.

If a desktop application does need to write to HKLM then it should consider separating those parts of the application that need to run elevated into a separate process. Otherwise the users are going to be very fed up with having to go through a UAC dialog in order to run your application. Even if they aren't using the part of the application that writes to HKLM. And if you force the entire app to require elevation then standard users can never run it at all.

The reason you can't create the key under HKEY_LOCAL_MACHINE while running Visual Studio is because Visual Studio isn't running as an elevated process.

For end-users the manifest of the application needs to indicate that full Administrator privileges are required. Here is the documentation on embedding a manifest for UAC

If the registry key doesn't need to be global on the machine consider writing to HKEY_CURRENT_USER instead.