I am going to attempt to answer my own question (as my experience may help others). Firstly, regarding the issue I experienced, I found this blog helpful (as were the comments from Sean Gallardy above).

As I had no Service Master Key (SMK) backup to restore from, my intention was to regenerate a new SMK using the ALTER SERVICE MASTER KEY REGENERATE with the FORCE option (causing loss of encrypted entities). I was prepared to have to recreate my credential secrets and Linked Server passwords. This instance had no Database Master Keys but, had it done so, I could have opened them using their password and regenerated them by the SMK (thus avoiding data loss).

However, I decided first to see if a simple restart of the SQL Server instance would resolve the issue - and it did! Upon restart, the Service Master Key verified successfully (and I confirmed this by creating a new test credential successfully).

My best guess is that whatever issue prevented the SMK verification previously (causing the "Service Master Key could not be decrypted using one of its encryptions" error log entry) had disappeared. I know that the SMK always has two encryptions: the machine key encryption and the service account encryption (and these provide an either-or decryption method in the case of cluster failover or service account change).

As the host WINTEL server was having issues, I imagine that invalidated the machine key encryption. I can't imagine what might have been invalidating the service account encryption (that account did not change) but whatever it was, it seemed to be a temporary problem. So my best guess is that, upon restart, the SMK was able to self-verify using the service account encryption (and, at that point, create a new machine key encryption).

The official solution as per Microsoft article is:

To work around this problem, add the domain user account to the SQLServer2005MSSQLUser$ComputerName$InstanceName domain group.

To do this, follow these steps:
1. Click Start, point to Administrative Tools, and then click Active Directory Users and Computers.
2. In the Active Directory Users and Computers snap-in, click Users.
3. Double-click SQLServer2005MSSQLUser$ComputerName$InstanceName.
4. In the Properties dialog box, click the Members tab.
5. On the Members tab, click Add.
6. In the Select Users, Contacts, Computers, or Groups dialog box, type the user in the DomainName\UserName format under Enter the object names to select, and then click OK. 7. In the Properties dialog box, click OK.

References

• Error message when you change the service account of SQL Server 2008 components to a non-domain administrator account on a Windows Server 2008 domain controller: "The service did not start due to a logon failure" or "WMI Provider Error" (Microsoft Support)

• WMI Provider Error - When Changing SQL Services Account (SQLServerCentral)

SQL Server Configuration Manager

When you run the SQL Server Configuration Manager and modify settings the configuration manager will add and remove permissions on files and directories based on the configuration changes made.

This is why Microsoft states, that configuration changes should always be made with the SQL Server Configuration Manager.

Important
Always use SQL Server tools such as SQL Server Configuration Manager to change the account used by the SQL Server or SQL Server Agent services, or to change the password for the account. In addition to changing the account name, SQL Server Configuration Manager performs additional configuration such as setting permissions in the Windows Registry so that the new account can read the SQL Server settings. Other tools such as the Windows Services Control Manager can change the account name but do not change associated settings. If the service cannot access the SQL Server portion of the registry the service may not start properly.

Reference: SQL Server Configuration Manager (Microsoft Docs)

Actual Steps To Perform

In your case you might have performed several of the steps, but not in the correct order. Try the following:

1. Open SQL Server Configuration Manager
2. Set the SQL Server (INSTANCE) service account to a user you don't want the service to run under
3. Restart the SQL Server (INSTANCE) service for your instance (should fail)
4. Close SQL Server Configuration Manager
5. Add the service account that you want the SQL Server service to run under to the specified group (as detailed at the beginning of the post; steps 1-7)
6. Open SQL Server Configuration Manager
7. Set the SQL Server (INSTANCE) service account to the user you just added to the SQLServer2005MSSQLUser$ComputerName$InstanceName group.
8. Restart SQL Server (INSTANCE) service for your instance

In the case that this doesn't work you may have broken ACLs (permissions) at some level in the SQL Server Program Files structure.

SQL Server Accounts And ACLs

Your service still isn't starting and it could still be an issue with permissions (ACLs)?

Then you might have to fix the file/folder permissions. The full list of SQL Server Account and the required permissions are listed in the following exhaustive documentations:

• Setting Up Windows Service Accounts (Microsoft Technet / 2008R2)
• Configure Windows Service Accounts and Permissions (Microsoft SQL Docs / 2012)

Everywhere where MSSQLServer is referenced in the documentation, replace with the account you wish to run your SQL Server (INSTANCE) with.

For example when checking the Reviewing Access Control Lists Created for SQL Server Service Accounts section of the document, ensure that your YourServiceAccount has access to:

Service Account for | Files and Folders        | Access
--------------------+--------------------------+---------------
MSSQLServer         | Instid\MSSQL\backup      | Full control
                    | Instid\MSSQL\binn        | Read, Execute
                    | Instid\MSSQL\data        | Full control
....

Instead of MSSQLServer use YourServiceAccount.

References:

• Setting Up Windows Service Accounts (Microsoft Technet / 2008R2)
• Configure Windows Service Accounts and Permissions (Microsoft SQL Docs / 2016+)